I encountered the following property:
If you take a number, add up its digits, square it, take the resulting number, and repeat the process after a finite number of steps, you will get 1, 81, 169, or 256 only as the answer.
(Actually, the 169 and 256 will keep alternating.)
For all numbers I tried, it was true, but I could not prove it mathematically.
Also, the answer would be 81 if the number is divisible by 3, but again I cannot prove it.
Can anyone give me a hint as I would like to complete it myself?
Best Answer
Let $S(m)$ be the digit sum of $m$ in the decimal system.
Let $N:=\displaystyle\sum_{k=0}^{m}10^ka_k$ (where $a_k$ are integers satisfying $0\le a_k\le 9$ and $a_m\not=0$) be the number we first take. Then, we have $N\rightarrow (S(N))^2$.
Here, we can say that if $m\ge 4$, then $$N\gt (S(N))^2=\bigg(\sum_{k=0}^{m}a_k\bigg)^2\tag1$$
A proof of $(1)$ is written at the end of this answer.
From $(1)$, we can say that, after a finite number of steps, we get a number $M_1$ satisfying $M_1\le 9999$.
Then, we get a square number $M_2^2$ satisfying $M_2^2\le (9+9+9+9)^2=36^2=1296$ since if $m\le 9999$, then the max of $S(m)$ is $S(9999)=36$.
Then, we get a square number $M_3^2$ satisfying $M_3^2\le (9+9+9)^2=27^2=729$ since if $m\le 1296$, then the max of $S(m)$ is $S(999)=27$. (proof : Suppose that there is $m$ satisfying $m\le 1296, S(m)\ge 27$ and $m=\overline{1abc}$. Then, we have $a+b+c\ge 26$. Since $a\le 2$, we have $b+c\ge 24$ which is impossible.)
Then, we get a square number $M_4^2$ satisfying $M_4^2\le (6+9+9)^2=24^2=576$ since if $m\le 729$, then the max of $S(m)$ is $S(699)=24$. (proof : Suppose that there is $m$ satisfying $m\le 729, S(m)\ge 24$ and $m=\overline{7ab}$. Then, we have $a+b\ge 17$. Since $a\le 2$, we get $b\ge 15$ which is impossible.)
Then, we get a square number $M_5^2$ satisfying $M_5^2\le (4+9+9)^2=22^2=484$ since if $m\le 576$, then the max of $S(m)$ is $S(499)=22$. (proof : Suppose that there is $m$ satisfying $m\le 576,S(m)\ge 22$ and $m=\overline{5ab}$. Then, we have $a+b\ge 17$. Since $a\le 7$, we have $b\ge 10$ which is impossible.)
Then, we get a square number $M_6^2$ satisfying $M_6^2\le (3+9+9)^2=21^2=441$ since if $m\le 484$, then the max of $S(m)$ is $S(399)=21$. (proof : Suppose that there is $m$ satisfying $m\le 484,S(m)\ge 21$ and $m=\overline{4ab}$. Then, we have $a+b\ge 17$. Since $a\le 8$, we have $b=9$, and so $a=8$ and $m=489$ which is impossible.)
$21^2\rightarrow 9^2$
$20^2\rightarrow \color{red}{4^2}\rightarrow \color{blue}{7^2}\rightarrow 13^2$
$19^2\rightarrow \color{purple}{10^2}\rightarrow 1^2$
$18^2\rightarrow 9^2$
$17^2\rightarrow 19^2$
$15^2\rightarrow 9^2$
$14^2\rightarrow 16^2$
$12^2\rightarrow 9^2$
$11^2\rightarrow \color{red}{4^2}$
$8^2\rightarrow \color{purple}{10^2}$
$6^2\rightarrow 9^2$
$5^2\rightarrow \color{blue}{7^2}$
$3^2\rightarrow 9^2$
$2^2\rightarrow \color{red}{4^2}$
Therefore, the claim follows.
In the following, let us prove that if $m\ge 4$, then $$N\gt (S(N))^2=\bigg(\sum_{k=0}^{m}a_k\bigg)^2\tag1$$
Proof : We have $N=\displaystyle\sum_{k=0}^{m}10^ka_k\ge 10^m$ and $(9(m+1))^2\ge\bigg(\displaystyle\sum_{k=0}^{m}a_k\bigg)^2$.
So, in order to prove $(1)$, it is sufficient to prove by induction on $m$ that $10^m\gt (9(m+1))^2$.
For $m=4$, it holds since $10^4-(9\times 5)^2=7975>0$.
Suppose that $10^m\gt (9(m+1))^2$. Then, we have $$\begin{align}&10^{m+1}-(9(m+2))^2 \\\\&=10\cdot 10^m-(9(m+2))^2 \\\\&\gt 10(9(m+1))^2-(9(m+2))^2 \\\\&=81(9m^2+16m+6) \\\\&\gt 0.\ \square\end{align}$$