Sequence of Sum of Squares of Digits

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$