The squared sum of all digits after finite repetition always returns a single digit number.

Question

While I was dealing with the Happy Number problem, I came across another question. Will after a certain finite iteration, the sum of squared digits of a number eventually become a single number. For example: $23 \to 2^2 + 3^2 = 13 \to 1^2 + 3^2 = 10 \to 1^2 + 0^2 = 1$. This is a single number. Is it true for every number ? And are there any explanation for it ? Thanks everyone.

Answer 1

Note the cycle:

$$4\mapsto 16\mapsto 37\mapsto 58\mapsto 89\mapsto 145\mapsto 42\mapsto 20\mapsto 4$$

We now claim that every natural number either reaches $1$ or enters this cycle.

This is easily confirmed for any particular $n$. To see that it holds generally, we'd like to use induction. To do that, however, we'd like to argue that $f(n)<n$, where, of course, $f(n)$ denotes the sum of the squared digits. This is false generally, but it is true for large enough $n$. To estimate what "large enough" means, note that $$f(n)≤81(\log_{10}(n)+1)$$ where the $\log_{10}$ term is an upper bound on the number of digits in $n$ and, of course, $81=9^2$.

We remark that $$n>280\implies 81(\log_{10}(n)+1)<n$$

so we only need to check up to $n=279$. In reality, checking up to $99$ suffices but perhaps it is easier to simply check up to $279$. Either way, the manual check is easy.

Answer 2

Here is another link to the same paper provided in the comments. The main reason this happens (and in fact will happen in any base if we are satisfied with repetitions) is that the operation you are talking about usually makes a number smaller. Taking inspiration from the paper, define

$$G_b(A)=\sum_{i=0}^r x_i^2$$

where $A$ can be written (in base $b$) as

$$A=\sum_{i=0}^r b^i x_i$$

Note that $0\leq x_i<b$ and that $x_r\neq 0$. Then for any $A$ such that $r\geq b+1$ we have

$$G_b(A)\leq \sum_{i=0}^r (b-1)^2=r(b-1)^2$$

Coupled with

$$A=\sum_{i=0}^r b^i x_i\geq \sum_{i=0}^{r-1} b^i (b-1)=b^{r}-1$$

For $b=2$ we have that

$$G_b(A)\leq r<2^r-1\leq A$$

For $b\geq 3$ we can use the fact

$$G_b(A)\leq r(b-1)^2\leq r(r-2)^2\leq r^3<3^r-1\leq b^r-1\leq A$$

Either way, we get that for all but a finite number of $A$

$$G_b(a)<A$$

But then, we only have to check these $b^{b+1}$ numbers and find where we get cycles.