Sequence of Sum of Squares of Digits

From ProofWiki
Jump to navigation Jump to search

Theorem

For a positive integer $n$, let $\map f n$ be the integer created by adding the squares of digits of $n$.

Let $m \in \Z_{>0}$ be expressed in decimal notation.


Let $\sequence {S_m}_{n \mathop \in \Z_{>0} }$ be the sequence defined as follows:

$n_k = \begin{cases} m & : n = 1 \\ \map f {n_{k - 1} } & : n > 1 \end{cases}$


Then eventually either $\sequence {S_m}$ sticks at $1$, or goes into the cycle:

$\ldots, 4, 16, 37, 58, 89, 145, 42, 20, 4, \ldots$


Proof

First note that:

$1^2 + 9^2 + 9^2 = 163$
$9^2 + 9^2 + 9^2 = 243$

and it can be seen that for a positive integer $m$ larger than $199$, $\map f m < m$.

Thus it is necessary to investigate numbers only up as far as that.


Starting from the bottom, we have that:

$\map f 1 = 1^2 = 1$

and so $\sequence {S_1} = 1, 1, 1, \ldots$


We note the sequence:

\(\ds \map f 4 \ \ \) \(\, \ds = \, \) \(\ds 4^2\) \(=\) \(\ds 16\)
\(\ds \map f {16} \ \ \) \(\, \ds = \, \) \(\ds 1^2 + 6^2\) \(=\) \(\ds 37\)
\(\ds \map f {37} \ \ \) \(\, \ds = \, \) \(\ds 3^2 + 7^2\) \(=\) \(\ds 58\)
\(\ds \map f {58} \ \ \) \(\, \ds = \, \) \(\ds 5^2 + 8^2\) \(=\) \(\ds 89\)
\(\ds \map f {89} \ \ \) \(\, \ds = \, \) \(\ds 8^2 + 9^2\) \(=\) \(\ds 145\)
\(\ds \map f {145} \ \ \) \(\, \ds = \, \) \(\ds 1^2 + 4^2 + 5^2\) \(=\) \(\ds 42\)
\(\ds \map f {42} \ \ \) \(\, \ds = \, \) \(\ds 4^2 + 2^2\) \(=\) \(\ds 20\)
\(\ds \map f {20} \ \ \) \(\, \ds = \, \) \(\ds 2^2 + 0^2\) \(=\) \(\ds 4\)

Hence any $m$ in the set $\set {4, 16, 20, 37, 42, 58, 89, 145}$ stays within that sequence, which we will refer to as $\SS$.

It remains to test the rest.


Let $\TT$ be the set of integers $m$ for which $S_m$ ends up either in $\SS$ or $1$.

Then the elements of $\SS$ are all in $\TT$, as is $1$.


If $m \in \TT$, then any integer $m'$ whose non-zero digits are the same as those of $m$ is also in $\TT$.

Thus:

$2, 10, 24, 40, 61, 73, 85, 98, 100, 106 \in \TT$


We use the notation:

$a \to b \to c$

to denote:

$\map f a = b, \map f b = c$

and work progressively through $\Z_{>0}$.

So:

\(\ds 3 \to 9 \to 81 \to 65 \to 61\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 18, 30, 56, 90\) \(\in\) \(\ds \TT\)
\(\ds 5 \to 25 \to 29 \to 85\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 50, 52, 92\) \(\in\) \(\ds \TT\)
\(\ds 6 \to 36 \to 45 \to 41 \to 17 \to 50\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 14, 54, 60, 63, 71\) \(\in\) \(\ds \TT\)
\(\ds 7 \to 49 \to 97 \to 130 \to 10\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 13, 31, 70, 79, 94\) \(\in\) \(\ds \TT\)
\(\ds 8 \to 64 \to 52\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 46, 80\) \(\in\) \(\ds \TT\)
\(\ds 11 \to 2\) \(\in\) \(\ds \TT\)
\(\ds 12 \to 5\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 21\) \(\in\) \(\ds \TT\)
\(\ds 15 \to 26 \to 40\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 51, 62\) \(\in\) \(\ds \TT\)
\(\ds 19 \to 82 \to 68 \to 100\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 28, 86, 91\) \(\in\) \(\ds \TT\)
\(\ds 22 \to 8\) \(\in\) \(\ds \TT\)
\(\ds 23 \to 13\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 32\) \(\in\) \(\ds \TT\)
\(\ds 27 \to 53 \to 34 \to 25\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 35, 43, 72\) \(\in\) \(\ds \TT\)
\(\ds 33 \to 18\) \(\in\) \(\ds \TT\)
\(\ds 38 \to 73\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 83\) \(\in\) \(\ds \TT\)
\(\ds 39 \to 90\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 93\) \(\in\) \(\ds \TT\)
\(\ds 44 \to 32\) \(\in\) \(\ds \TT\)
\(\ds 47 \to 65\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 74\) \(\in\) \(\ds \TT\)
\(\ds 48 \to 80\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 84\) \(\in\) \(\ds \TT\)
\(\ds 55 \to 50\) \(\in\) \(\ds \TT\)
\(\ds 57 \to 74\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 75\) \(\in\) \(\ds \TT\)
\(\ds 59 \to 106\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 95\) \(\in\) \(\ds \TT\)
\(\ds 66 \to 72\) \(\in\) \(\ds \TT\)
\(\ds 67 \to 85\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 76\) \(\in\) \(\ds \TT\)
\(\ds 69 \to 117 \to 51\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 96\) \(\in\) \(\ds \TT\)
\(\ds 77 \to 98\) \(\in\) \(\ds \TT\)
\(\ds 78 \to 113 \to 11\) \(\in\) \(\ds \TT\)
\(\ds \leadsto \ \ \) \(\ds 87\) \(\in\) \(\ds \TT\)
\(\ds 88 \to 128 \to 69\) \(\in\) \(\ds \TT\)
\(\ds 99 \to 162 \to 41\) \(\in\) \(\ds \TT\)




Sources