DivideByNineMethod China Difficult

Problem - 4245
Let $n$ be a positive integer and function $S_1(n)$ return the square of the sum of $n$'s digits. Additionally, let $S_{k+1}(n)=S_1\left(S_k(n)\right)$, where $k$ is a positive integer. Find the value of $S_{1991}(2^{1990})$.

Answer     256

Let $N=2^{1990}$. First, because $2^{1990} < 8^{664} < 10^{664}$, $N$ has at most $664$ digits. Therefore $$S_1(N) < (9\times 664)^2 < 4\times 10^7$$

Using a similar reasoning, we have $$\begin{array}{ll} S_2(N) & \le (3 + 9\times 7)^2 < 4400\\ S_3(N) &\le (3 + 9\times 3)^2 < 900 = 30^2 \end{array}$$

By definition, values of all $S_{k+1}(n)$ are square numbers whose square root is the sum of the digits of $S_k(n)$. Let $S_2(N) = a$. Then we have $S_3(N)=a^2$ and $a < 30$. With the MOD by $9$ technique, we have $$a\equiv \left(S_1(N)\right)^2\equiv N^4\equiv 8^{2653}\times 2\equiv -2\equiv 7\pmod{9}$$

Because $0 < a < 30$, $a=7$, $16$, or $25$. Therefore, $S_3(N) = 49$, $256$, or $625$. And, $S_4(N) = 169$, $S_5(N)=256$, $S_6(N)=169$.

Now, it is clear that the value of $S_k(N)$ will alternate and $S_{1991}(N) = \boxed{256}$.

report an error