Repeated sum of square of digits always arrives at $1$ or $89$

Question

I found an astonishing result in a problem today here !
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

$44 \to 32 \to 13 \to 10 \to 1 \to 1$

$85 \to 89 \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to 89$

Therefore any chain that arrives at $1$ or $89$ will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at $1$ or $89$.
Why is this true?

Answer 1

Let $s(n)$ be the function that adds the square of the digits in $n$.

Note that for $r\geq 3$, and $d_k\in\{0,1,\dots 9\}$ for $k=1,2,\dots, r$ with $d_r\geq 1$, we have that $$n=d_0+\sum_{k=1}^{r-1} d_k 10^k+d_r10^r >d_0^2+\sum_{k=1}^{r-1} d_k^2+d_r^2=s(n)$$ because $10>d_k$ and $d_0 +d_r10^r\geq 1000\geq 9^2+9^2\geq d_0^2+d_r^2$.

Therefore if $n$ has at least three digits then $n>s(n)$. This implies that eventually we will obtain a number of at most three digits. So it suffices to check what happens for the integers in $[1,999]$: it can be verified that given $n\in [1,999]$, then $s^{(k)}(n)\in\{1,89\}$ with $k\leq 11$.

Hence, we may conclude that for any $n\geq 1$ the sequence, after a finite number of steps, will enter in one of the two cycles: $$(1)\quad \mbox{or}\quad (89,145,42,20,4,16,37,58).$$

Answer 2

I suppose you're excluding $0$.

If $x$ has $n$ digits, the sum of squares of the digits of $x$ is at most $81 n$, and that has at most $1 + \log_{10}(81 n)$ digits. Now $1 + \log_{10}(81 n) < n$ if $n \ge 4$, so eventually you get to a number of at most $3$ digits. Check all $999$ positive numbers of at most 3 digits, and you'll find that they all end up at $1$ or $89$.

EDIT: Although not so easy to see immediately, it turns out that the sum of squares of the digits of any $3$-digit number is less than the number, so we can restrict our attention to numbers of $2$ or fewer digits.

Answer 3

Let us observe that, for any function $g: \mathbb{N} \to \mathbb{N}$, if we apply $g$ repeatedly to $n$ we will eventually arrive at a positive integer $k$ such that $g(k) \ge k$. Why? Because if not, then $n > g(n) > g(g(n)) > g(g(g(n))) > \cdots$, but this can only go on finitely long since $g$ lies in the positive integers.

Therefore the same is true of $f$, and it suffices to consider only values of $\boldsymbol{n}$ for which $\boldsymbol{f(n) \ge n}$. Let us search for all such values.

• First, $n$ must have $3$ or less digits. Others have already proven this, but let $k$ be the number of digits of $n$. Then the sum of the squares of the digits (i.e. $f(n)$) is at most $81k$. On the other hand, $n$ is at least $10^{k-1}$. So $n$ is very large but $f(n)$ is much smaller. Formally, we can say that if $\boldsymbol{k \ge 4}$ then $10^{k-1} > 81k$ so $$ n \ge 10^{k-1} > 81k \ge f(n). $$ Therefore, $f(n) < n$ for all $n$ with four or more digits, i.e. for all $n \ge 1000$. So we can assume $1 \le n \le 999$.

• Now let's assume $n$ has three digits: $n = 100a + 10b + c$, where $a \ge 1$. We need $a^2 + b^2 + c^2 \ge 100a$, so $$ 100a \le 3 \cdot 9^2 = 243, $$ so $a = 1$ or $a = 2$. But now $100a \le a^2 + b^2 + c^2 \le 4 + 2 \cdot 9^2 = 166$, so $a = 1$. So we need $1 + b^2 + c^2 \ge 100 + 10b + c$, or in other words $b^2 + c^2 - 10b - c \ge 99$. Now $b^2 - 10b < 0$, so the best we can do is $9^2 - 9 < 99$, so this is impossible.

• So we are left with considering $n = 10a + b$. Now we are simply solving the inequality $a^2 + b^2 \ge 10a + b$, for $0 \le a, b \le 9$. The inequality can be rewritten $$ b(b-1) \ge a(10 - a). $$ This leads to the following solutions for $n$: \begin{align*} a = 0 &\implies n = 1, 2, 3, 4, 5, 6, 7, 8, 9 \\ a = 1 &\implies n = 14, 15, 16, 17, 18, 19 \\ a = 2 &\implies n = 25, 26, 27, 28, 29 \\ a = 3 &\implies n = 36, 37, 38, 39 \\ a = 4 &\implies n = 46, 47, 48, 49 \\ a = 5 &\implies n = 56, 57, 58, 59 \\ a = 6 &\implies n = 66, 67, 68, 69 \\ a = 7 &\implies n = 76, 77, 78, 79 \\ a = 8 &\implies n = 85, 86, 87, 88, 89 \\ a = 9 &\implies n = 94, 95, 96, 97, 98, 99. \end{align*} So we need to show that applying $f$ repeatedly to any of the above will get $1$ or $89$. This can be done quite simply, by repeatedly applying $f$ to each individual element; for example, $$ 2 \to 4 \to 16 \to 37 \to 58 \to 89 $$ which knocks out $6$ of the above possibilities. And $$ 3 \to 9 \to (81) \to 17 \to (50) \to 25 \to 29 \to 85 \to 89, $$ knocking out several more (I put numbers $n$ such that $f(n) < n$ in parentheses, since we don't care about them.) We can proceed in this manner, just checking what happens for a specific value, until all of the numbers above are accounted for, and then we have proven that we will eventually arrive at $1$ or $89$.

As others have pointed out, while $f(1) = 1$, $89$ is not so special -- we don't have $f(89) = 89$, but instead it is part of a cycle of $8$ numbers.