perfect digital invariant

Let $n$ be a natural number. The perfect digital invariant function (also known as a happy function, from happy numbers) for base $b\; >\; 1$ and power $p\; >\; 0$ $F\_\{p,\; b\}\; :\; \backslash mathbb\{N\}\; \backslash rightarrow\; \backslash mathbb\{N\}$ is defined as:

:$F\_\{p,\; b\}(n)\; =\; \backslash sum\_\{i=0\}^\{k\; -\; 1\}\; d\_i^p.$

where $k\; =\; \backslash lfloor\; \backslash log\_\{b\}\{n\}\; \backslash rfloor\; +\; 1$ is the number of digits in the number in base $b$, and

:$d\_i\; =\; \backslash frac\{n\; \backslash bmod\{b^\{i+1\}\}\; -\; n\; \backslash bmod\; b^i\}\{b^i\}$

is the value of each digit of the number. A natural number $n$ is a perfect digital invariant if it is a fixed point for $F\_\{p,\; b\}$, which occurs if $F\_\{p,\; b\}(n)\; =\; n$. $0$ and $1$ are trivial perfect digital invariants for all $b$ and $p$, all other perfect digital invariants are nontrivial perfect digital invariants.

For example, the number 4150 in base $b\; =\; 10$ is a perfect digital invariant with $p\; =\; 5$, because $4150\; =\; 4^5\; +\; 1^5\; +\; 5^5\; +\; 0^5$.

A natural number $n$ is a sociable digital invariant if it is a periodic point for $F\_\{p,\; b\}$, where $F\_\{p,b\}^k(n)\; =\; n$ for a positive integer $k$ (here $F\_\{p,b\}^k$ is the $k$th iterate of $F\_\{p,b\}$), and forms a cycle of period $k$. A perfect digital invariant is a sociable digital invariant with $k\; =\; 1$, and a amicable digital invariant is a sociable digital invariant with $k\; =\; 2$.

All natural numbers $n$ are preperiodic points for $F\_\{p,\; b\}$, regardless of the base. This is because if $k\; \backslash geq\; p\; +\; 2$, $n\; \backslash geq\; b^\{k-1\}\; >\; b^p\; k$, so any $n$ will satisfy $n\; >\; F\_\{b,p\}(n)$ until . There are a finite number of natural numbers less than $b^\{p+1\}$, so the number is guaranteed to reach a periodic point or a fixed point less than $b^\{p+1\}$, making it a preperiodic point.

Numbers in base $b\; >\; p$ lead to fixed or periodic points of numbers $n\; \backslash leq\; (p\; -\; 2)^p\; +\; p\; (b\; -\; 1)^p$.

{{Math proof|title=Proof|drop=hidden|proof=

If $b\; >\; p$, then the bound can be reduced.

Let $r$ be the number for which the sum of squares of digits is largest among the numbers less than $b^p$.

:$r\; =\; b^p\; -\; 1\; =\; \backslash sum\_\{t=0\}^p\; (b\; -\; 1)b^t$

: because $b\; \backslash geq\; (p\; +\; 1)$

Let $s$ be the number for which the sum of squares of digits is largest among the numbers less than $(p\; +\; 1)(b\; -\; 1)^p$.

:$s\; =\; (p\; +\; 1)b^p\; -\; 1\; =\; p\; b^p\; +\; \backslash sum\_\{t=0\}^\{p\; -\; 1\}\; (b\; -\; 1)b^t$

: because $b\; \backslash geq\; p$

Let $t$ be the number for which the sum of squares of digits is largest among the numbers less than $p\; b^p$.

:$t\; =\; (p\; -\; 1)\; b^p\; +\; \backslash sum\_\{t=0\}^\{p\; -\; 1\}\; (b\; -\; 1)b^t$

:$F\_\{p,\; b\}(t)\; =\; (p\; -\; 1)^p\; +\; p\; (b\; -\; 1)^p$

Let $u$ be the number for which the sum of squares of digits is largest among the numbers less than $F\_\{p,\; b\}(t)\; +\; 1$.

:$u\; =\; (p\; -\; 2)\; b^p\; +\; \backslash sum\_\{t=0\}^\{p\; -\; 1\}\; (b\; -\; 1)b^t$

:

. Thus, numbers in base $b\; >\; p$ lead to cycles or fixed points of numbers $n\; \backslash leq\; F\_\{p,\; b\}(u)\; =\; (p\; -\; 1)^p\; +\; p\; (b\; -\; 1)^p$.

}}

The number of iterations $i$ needed for $F\_\{p,b\}^\{i\}(n)$ to reach a fixed point is the perfect digital invariant function's persistence of $n$, and undefined if it never reaches a fixed point.

$F\_\{1,\; b\}$ is the digit sum. The only perfect digital invariants are the single-digit numbers in base $b$, and there are no periodic points with prime period greater than 1.

$F\_\{p,\; 2\}$ reduces to $F\_\{1,\; 2\}$, as for any power $p$, $0^p\; =\; 0$ and $1^p\; =\; 1$.

For every natural number $k\; >\; 1$, if , $(b\; -\; 1)\; \backslash equiv\; 0\; \backslash bmod\; k$ and $(p\; -\; 1)\; \backslash equiv\; 0\; \backslash bmod\; \backslash phi(k)$, then for every natural number $n$, if $n\; \backslash equiv\; m\; \backslash bmod\; k$, then $F\_\{p,\; b\}(n)\; \backslash equiv\; m\; \backslash bmod\; k$, where $\backslash phi(k)$ is Euler's totient function.

{{Math proof|title=Proof|drop=hidden|proof=

Let

:$n\; =\; \backslash sum\_\{i\; =\; 0\}^j\; d\_i\; b^i$

be a natural number with $j$ digits, where , and $(b\; -\; 1)\; \backslash equiv\; 0\; \backslash bmod\; k$, where $k$ is a natural number greater than 1.

According to the divisibility rules of base $b$, if $b\; -\; 1\; \backslash equiv\; 0\; \backslash bmod\; k$, then if $n\; \backslash equiv\; m\; \backslash bmod\; k$, then the digit sum

: $F\_\{1,\; b\}(n)\; =\; \backslash sum\_\{i\; =\; 0\}^j\; d\_i\; \backslash equiv\; m\; \backslash bmod\; k$

If a digit $d\_i\; \backslash equiv\; m\; \backslash bmod\; k$, then $d\_i^p\; \backslash equiv\; m^p\; \backslash bmod\; k$. According to Euler's theorem, if $(p\; -\; 1)\; \backslash equiv\; 0\; \backslash bmod\; \backslash phi(k)$, $m^p\; \backslash bmod\; k\; =\; m\; \backslash bmod\; k$. Thus, if the digit sum $F\_\{1,\; b\}(n)\; \backslash equiv\; m\; \backslash bmod\; k$, then $F\_\{p,\; b\}(n)\; \backslash equiv\; m\; \backslash bmod\; k$.

Therefore, for any natural number $k$, if , $(b\; -\; 1)\; \backslash equiv\; 0\; \backslash bmod\; k$ and $(p\; -\; 1)\; \backslash equiv\; 0\; \backslash bmod\; \backslash phi(k)$, then for every natural number $n$, if $n\; \backslash equiv\; m\; \backslash bmod\; k$, then $F\_\{p,\; b\}(n)\; \backslash equiv\; m\; \backslash bmod\; k$.

}}

No upper bound can be determined for the size of perfect digital invariants in a given base and arbitrary power, and it is not currently known whether or not the number of perfect digital invariants for an arbitrary base is finite or infinite.

By definition, any three-digit perfect digital invariant $n\; =\; d\_2\; d\_1\; d\_0$ for $F\_\{2,\; b\}$ with natural number digits , , has to satisfy the cubic Diophantine equation $d\_0^2\; +\; d\_1^2\; +\; d\_2^2\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$. $d\_2$ has to be equal to 0 or 1 for any $b\; >\; 2$, because the maximum value $n$ can take is . As a result, there are actually two related quadratic Diophantine equations to solve:

: $d\_0^2\; +\; d\_1^2\; =\; d\_1\; b\; +\; d\_0$ when $d\_2\; =\; 0$, and

: $d\_0^2\; +\; d\_1^2\; +\; 1\; =\; b^2\; +\; d\_1\; b\; +\; d\_0$ when $d\_2\; =\; 1$.

The two-digit natural number $n\; =\; d\_1\; d\_0$ is a perfect digital invariant in base

: $b\; =\; d\_1\; +\; \backslash frac\{d\_0\; (d\_0\; -\; 1)\}\{d\_1\}.$

This can be proven by taking the first case, where $d\_2\; =\; 0$, and solving for $b$. This means that for some values of $d\_0$ and $d\_1$, $n$ is not a perfect digital invariant in any base, as $d\_1$ is not a divisor of $d\_0\; (d\_0\; -\; 1)$. Moreover, $d\_0\; >\; 1$, because if $d\_0\; =\; 0$ or $d\_0\; =\; 1$, then $b\; =\; d\_1$, which contradicts the earlier statement that .

There are no three-digit perfect digital invariants for $F\_\{2,\; b\}$, which can be proven by taking the second case, where $d\_2\; =\; 1$, and letting $d\_0\; =\; b\; -\; a\_0$ and $d\_1\; =\; b\; -\; a\_1$. Then the Diophantine equation for the three-digit perfect digital invariant becomes

: $(b\; -\; a\_0)^2\; +\; (b\; -\; a\_1)^2\; +\; 1\; =\; b^2\; +\; (b\; -\; a\_1)\; b\; +\; (b\; -\; a\_0)$

: $b^2\; -\; 2\; a\_0\; b\; +\; a\_0^2\; +\; b^2\; -\; 2\; a\_1\; b\; +\; a\_1^2\; +\; 1\; =\; b^2\; +\; (b\; -\; a\_1)\; b\; +\; (b\; -\; a\_0)$

: $2\; b^2\; -\; 2\; (a\_0\; +\; a\_1)\; b\; +\; a\_0^2\; +\; a\_1^2\; +\; 1\; =\; b^2\; +\; (b\; -\; a\_1)\; b\; +\; (b\; -\; a\_0)$

: $b^2\; +\; (b\; -\; 2\; (a\_0\; +\; a\_1))\; b\; +\; a\_0^2\; +\; a\_1^2\; +\; 1\; =\; b^2\; +\; (b\; -\; a\_1)\; b\; +\; (b\; -\; a\_0)$

$2\; (a\_0\; +\; a\_1)\; >\; a\_1$ for all values of . Thus, there are no solutions to the Diophantine equation, and there are no three-digit perfect digital invariants for $F\_\{2,\; b\}$.

{{Quote frame|

There are just four numbers, after unity, which are the sums of the cubes of their digits:

:$153=1^3+5^3+3^3$

:$370=3^3+7^3+0^3$

:$371=3^3+7^3+1^3$

:$407=4^3+0^3+7^3.$

These are odd facts, very suitable for puzzle columns and likely to amuse amateurs, but there is nothing in them which appeals to the mathematician. {{OEIS|id=A046197}}|G. H. Hardy|A Mathematician's Apology}}

By definition, any four-digit perfect digital invariant $n$ for $F\_\{3,\; b\}$ with natural number digits , , , has to satisfy the quartic Diophantine equation $d\_0^3\; +\; d\_1^3\; +\; d\_2^3\; +\; d\_3^3\; =\; d\_3\; b^3\; +\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$. $d\_3$ has to be equal to 0, 1, 2 for any $b\; >\; 3$, because the maximum value $n$ can take is . As a result, there are actually three related cubic Diophantine equations to solve

: $d\_0^3\; +\; d\_1^3\; +\; d\_2^3\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ when $d\_3\; =\; 0$

: $d\_0^3\; +\; d\_1^3\; +\; d\_2^3\; +\; 1\; =\; b^3\; +\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ when $d\_3\; =\; 1$

: $d\_0^3\; +\; d\_1^3\; +\; d\_2^3\; +\; 8\; =\; 2\; b^3\; +\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ when $d\_3\; =\; 2$

We take the first case, where $d\_3\; =\; 0$.

Let $k$ be a positive integer and the number base $b\; =\; 3\; k\; +\; 1$. Then:

• $n\_1\; =\; kb^2\; +\; (2k\; +\; 1)b$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of $n\_1\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ be $d\_2\; =\; k$, $d\_1\; =\; 2k\; +\; 1$, and $d\_0\; =\; 0$. Then

: $$

\begin{align}

F_{3, b}(n_1) & = d_0^3 + d_1^3 + d_2^3 \\

& = k^3 + (2k + 1)^3 + 0^3 \\

& = (k^2 - k(2k + 1) + (2k + 1)^2)(k + (2k + 1)) \\

& = (k^2 - 2k^2 - k + 4k^2 + 4k + 1)(3k + 1) \\

& = (3k^2 + 3k + 1)(3k + 1) \\

& = (3k^2 + 4k + 1)(3k + 1) - k(3k + 1) \\

& = (k + 1)(3k + 1)(3k + 1) - k(3k + 1) \\

& = k(3k + 1)(3k + 1) + (3k + 1)(3k + 1) - k(3k + 1) \\

& = k(3k + 1)^2 + (2k + 1)(3k + 1) + 0 \\

& = d_2 b^2 + d_1 b + d_0 \\

& = n_1

\end{align}

Thus $n\_1$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

}}

• $n\_2\; =\; kb^2\; +\; (2k\; +\; 1)b\; +\; 1$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of $n\_2\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ be $d\_2\; =\; k$, $d\_1\; =\; 2k\; +\; 1$, and $d\_0\; =\; 1$. Then

:$$

\begin{align}

F_{3, b}(n_2) & = d_0^3 + d_1^3 + d_2^3 \\

& = k^3 + (2k + 1)^3 + 1^3 \\

& = (k^2 - k(2k + 1) + (2k + 1)^2)(k + (2k + 1)) + 1 \\

& = (k^2 - 2k^2 - k + 4k^2 + 4k + 1)(3k + 1) + 1 \\

& = (3k^2 + 3k + 1)(3k + 1) + 1 \\

& = (3k^2 + 4k + 1)(3k + 1) - k(3k + 1) + 1 \\

& = (k + 1)(3k + 1)(3k + 1) - k(3k + 1) + 1 \\

& = k(3k + 1)(3k + 1) + (3k + 1)(3k + 1) - k(3k + 1) + 1 \\

& = k(3k + 1)^2 + (2k + 1)(3k + 1) + 1 \\

& = d_2 b^2 + d_1 b + d_0 \\

& = n_2

\end{align}

Thus $n\_2$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

}}

• $n\_3\; =\; (k\; +\; 1)b^2\; +\; (2k\; +\; 1)$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of $n\_3\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ be $d\_2\; =\; k\; +\; 1$, $d\_1\; =\; 0$, and $d\_0\; =\; 2k\; +\; 1$. Then

:$$

\begin{align}

F_{3, b}(n_3) & = d_0^3 + d_1^3 + d_2^3 \\

& = (k + 1)^3 + 0^3 + (2k + 1)^3 \\

& = ((k + 1)^2 - (k + 1)(2k + 1) + (2k + 1)^2)((k + 1) + (2k + 1)) \\

& = ((k + 1)^2 + k(2k + 1)(3k + 2) \\

& = (k^2 + 2k + 1 + 2k^2 + k)(3k + 2) \\

& = (3k^2 + 3k + 1)(3k + 2) \\

& = (3k^2 + 3k)(3k + 2) + (3k + 2) \\

& = 3k(k + 1)(3k + 2) + (3k + 2) \\

& = (k + 1)((3k + 1)^2 - 1) + (3k + 2) \\

& = (k + 1)(3k + 1)^2 - (k + 1) + (3k + 2) \\

& = (k + 1)(3k + 1)^2 + 0(3k + 1) + (2k + 1) \\

& = d_2 b^2 + d_1 b + d_0 \\

& = n_3

\end{align}

Thus $n\_3$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

}}

Let $k$ be a positive integer and the number base $b\; =\; 3\; k\; +\; 2$. Then:

• $n\_1\; =\; kb^2\; +\; (2k\; +\; 1)$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of $n\_1\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ be $d\_2\; =\; k$, $d\_1\; =\; 2k\; +\; 1$, and $d\_0\; =\; 0$. Then

: $F\_\{3,\; b\}(n\_1)\; =\; d\_0^3\; +\; d\_1^3\; +\; d\_2^3$

:: $=\; k^3\; +\; 0^3\; +\; (2k\; +\; 1)^3$

:: $=\; (k^2\; -\; k(2k\; +\; 1)\; +\; (2k\; +\; 1)^2)(k\; +\; (2k\; +\; 1))$

:: $=\; (k^2\; -\; 2k^2\; -\; k\; +\; 4k^2\; +\; 4k\; +\; 1)(3k\; +\; 1)$

:: $=\; (3k^2\; +\; 3k\; +\; 1)(3k\; +\; 1)$

:: $=\; (3k^2\; +\; 3k\; +\; 1)(3k\; +\; 2)\; -\; (3k^2\; +\; 3k\; +\; 1)$

:: $=\; (3k^2\; +\; 3k\; +\; 1)(3k\; +\; 2)\; -\; (3k^2\; +\; 2k\; +\; k\; +\; 1)$

:: $=\; (3k^2\; +\; 3k\; +\; 1)(3k\; +\; 2)\; -\; k(3k\; +\; 2)\; -\; (k\; +\; 1)$

:: $=\; (3k^2\; +\; 2k\; +\; 1)(3k\; +\; 2)\; -\; (k\; +\; 1)$

:: $=\; (3k^2\; +\; 2k)(3k\; +\; 2)\; +\; (3k\; +\; 2)\; -\; (k\; +\; 1)$

:: $=\; k(3k\; +\; 2)^2\; +\; (2k\; +\; 1)$

:: $=\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$

:: $=\; n\_1$

Thus $n\_1$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

}}

Let $k$ be a positive integer and the number base $b\; =\; 6\; k\; +\; 4$. Then:

• $n\_4\; =\; kb^2\; +\; (3k\; +\; 2)b\; +\; (2k\; +\; 1)$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of $n\_4\; =\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$ be $d\_2\; =\; k\; +\; 1$, $d\_1\; =\; 3k\; +\; 2$, and $d\_0\; =\; 2k\; +\; 1$. Then

:$F\_\{3,\; b\}(n\_3)\; =\; d\_0^3\; +\; d\_1^3\; +\; d\_2^3$

::$=\; (k)^3\; +\; (3k\; +\; 2)^3\; +\; (2k\; +\; 1)^3$

::$=\; k^3\; +\; ((3k\; +\; 2)^2\; -\; (3k\; +\; 2)(2k\; +\; 1)\; +\; (2k\; +\; 1)^2)((3k\; +\; 2)\; +\; (2k\; +\; 1))$

::$=\; k^3\; +\; ((3k\; +\; 2)(k\; +\; 1)\; +\; (2k\; +\; 1)^2)(5k\; +\; 3)$

::$=\; k^3\; +\; (3k^2\; +\; 5k\; +\; 2\; +\; 4k^2\; +\; 4k\; +\; 1)(5k\; +\; 3)$

::$=\; k^3\; +\; (7k^2\; +\; 9k\; +\; 3)(5k\; +\; 3)$

::$=\; k^3\; +\; 5k(7k^2\; +\; 9k\; +\; 3)\; +\; 3(7k^2\; +\; 9k\; +\; 3)$

::$=\; k^3\; +\; 35k^3\; +\; 45k^2\; +\; 15k\; +\; 21k^2\; +\; 27k\; +\; 9$

::$=\; 36k^3\; +\; 66k^2\; +\; 42k\; +\; 9$

::$=\; (6k\; +\; 4)(6k^2)\; +\; 42k^2\; +\; 42k\; +\; 9$

::$=\; (6k\; +\; 4)(6k^2)\; +\; (6k\; +\; 4)(4k^2)\; +\; 18k^2\; +\; 26k\; +\; 9$

::$=\; (6k\; +\; 4)(6k^2\; +\; 4k)\; +\; 18k^2\; +\; 26k\; +\; 9$

::$=\; k(6k\; +\; 4)^2\; +\; (6k\; +\; 4)(3k)\; +\; 14k\; +\; 9$

::$=\; k(6k\; +\; 4)^2\; +\; (3k\; +\; 2)(6k\; +\; 4)\; +\; 2k\; +\; 1$

::$=\; d\_2\; b^2\; +\; d\_1\; b\; +\; d\_0$

:: $=\; n\_4$

Thus $n\_4$ is a perfect digital invariant for $F\_\{3,\; b\}$ for all $k$.

}}

All numbers are represented in base $b$.

Perfect digital invariants can be extended to the negative integers by use of a signed-digit representation to represent each integer.

In balanced ternary, the digits are 1, −1 and 0. This results in the following:

• With odd powers $p\; \backslash equiv\; 1\; \backslash bmod\; 2$, $F\_\{p,\; \backslash text\{bal\}3\}$ reduces down to digit sum iteration, as $(-1)^p\; =\; -1$, $0^p\; =\; 0$ and $1^p\; =\; 1$.
• With even powers $p\; \backslash equiv\; 0\; \backslash bmod\; 2$, $F\_\{p,\; \backslash text\{bal\}3\}$ indicates whether the number is even or odd, as the sum of each digit will indicate divisibility by 2 if and only if the sum of digits ends in 0. As $0^p\; =\; 0$ and $(-1)^p\; =\; 1^p\; =\; 1$, for every pair of digits 1 or −1, their sum is 0 and the sum of their squares is 2.

{{Main|Happy number}}

A happy number $n$ for a given base $b$ and a given power $p$ is a preperiodic point for the perfect digital invariant function $F\_\{p,\; b\}$ such that the $m$-th iteration of $F\_\{p,\; b\}$ is equal to the trivial perfect digital invariant $1$, and an unhappy number is one such that there exists no such $m$.

The example below implements the perfect digital invariant function described in the definition above to search for perfect digital invariants and cycles in Python. This can be used to find happy numbers.

def pdif(x: int, p: int, b: int) -> int:

"""Perfect digital invariant function."""

total = 0

while x > 0:

total = total + pow(x % b, p)

x = x // b

return total

def pdif_cycle(x: int, p: int, b: int) -> list[int]:

seen = []

while x not in seen:

seen.append(x)

x = pdif(x, p, b)

cycle = []

while x not in cycle:

cycle.append(x)

x = pdif(x, p, b)

return cycle

• Arithmetic dynamics
• Dudeney number
• Factorion
• Happy number
• Kaprekar's constant
• Kaprekar number
• Meertens number
• Narcissistic number
• Perfect digit-to-digit invariant
• Sum-product number

{{reflist}}

• [https://www.deimel.org/rec_math/DI_0.htm Digital Invariants]

{{Classes of natural numbers}}

Category:Arithmetic dynamics

Category:Articles with example Python (programming language) code

Category:Base-dependent integer sequences

Category:Diophantine equations