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:

\(\displaystyle \map f 4 \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 4^2\) \(=\) \(\displaystyle 16\)
\(\displaystyle \map f {16} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 1^2 + 6^2\) \(=\) \(\displaystyle 37\)
\(\displaystyle \map f {37} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 3^2 + 7^2\) \(=\) \(\displaystyle 58\)
\(\displaystyle \map f {58} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 5^2 + 8^2\) \(=\) \(\displaystyle 89\)
\(\displaystyle \map f {89} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 8^2 + 9^2\) \(=\) \(\displaystyle 145\)
\(\displaystyle \map f {145} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 1^2 + 4^2 + 5^2\) \(=\) \(\displaystyle 42\)
\(\displaystyle \map f {42} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 4^2 + 2^2\) \(=\) \(\displaystyle 20\)
\(\displaystyle \map f {20} \ \ \) \(\, \displaystyle = \, \) \(\displaystyle 2^2 + 0^2\) \(=\) \(\displaystyle 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 $\mathcal S$.

It remains to test the rest.


Let $\mathcal T$ be the set of integers $m$ for which $S_m$ ends up either in $\mathcal S$ or $1$.

Then the elements of $\mathcal S$ are all in $\mathcal T$, as is $1$.


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

Thus:

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


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:

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



Sources