2

I am helping a high school student to solve some challenging problems. I am stuck on the following problem: let $S(n)$ be a digit sum of the integer $n$, e.g. $S(1234)=10$. Find $S(S(S(S(2018^{2018}))))$.

I spent some time on this problem but was not able to solve it. I found out, that the result should be less than $10$, since the number of digits in a number $n$ is $[\log_{10}n]+1$, where $[]$ denotes rounding towards zero. But this is not really helpful, since I need the precise number as an answer, not just an estimate.

I've tried to find some iteration relatioship, e.g. what is $S(n\cdot m)$, but it didn't help either.

Hints are appreciated.

Thanks,

Mikhail

Mikhail Genkin
  • 194
  • 2
    Remember $S(n) \mod 9 \equiv n \mod 9$ so if the answer is less than 10 it must be $2018^{2018} \mod 9$.And $2018 \equiv 2$ les is $2^{2018}\mod 9$. $2^3 \equiv -1 \mod 94 so this is $2^{3672 + 2}\equiv (-1)^{672}2^2\equiv 4 \mod 9$. So the answer is $4$. – fleablood Dec 04 '17 at 23:17

2 Answers2

2

Remember $n \equiv S(n) \mod 9$. ($a \equiv b \mod n$ means $a$ and $b$ have the same remainder when divided by $n$.)[See postscript]

So $S(S(S(S(2018^{2018})))) \equiv 2018^{2018}\mod 9$. So what is the remainder of $2018^{2018}$ when divided by $9$.

As $2018 \equiv 2 \mod 9$ then $2018^{2018} \equiv 2^{2018} \mod 9$.

$2^3 = 8 \equiv -1 \mod 9$ so $2^{2018} = 2^{3*672 + 2} \equiv (2^3)^{672}*2^2 \equiv (-1)^{672}*4\equiv 4 \mod 9$.

So $2018^{2018}$ will have remainder $4$ when divided by $9$.

And therefore $S(S(S(S(2018^{2018}))) $ will also have remainder $4$ when divided by $9$.

Now you now that $0 < S(S(S(S(2018^{2018})))< 10$. So what single digit has remainder $4$ when divided by $9$. There is only one; $4$ itself.

==== post script ======

If $n = \sum 10^i a_i$ then $S(n) = \sum a_i$.

$n - S(n) = \sum 10^i a_i - \sum a_i = \sum (10^i- 1)a_i$.

$10^i - 1 = 999999......999$ so $n - S(n)$ has remainder $0$ when divided by $9$.

So $n$ and $S(n)$ must have the same remainder when divided by $9$.

fleablood
  • 124,253
2

For any positive integer $a$, $S(a)$ and $a$ have the same remainder on division by $9$.

Considering $2018^{2018}\bmod 9$, we have $2018\equiv 2\bmod 9$ and $2^6\equiv 1\bmod 9$. So $2018^{2018}\equiv 2^{2018}\equiv 1^{336}\cdot 2^2\equiv 4\bmod 9$.

Then since $2018^2<10^7, $ the number of digits in $E:= 2018^{2018}$ is less than $2018\cdot 7/2+1 < 8000$, so $S(E)< 9\cdot 8000 = 72000,$ $S(S(E)) \le 42,$ and $S(S(S(E)))) \le 12$

So you have more function iterations than you strictly need, but since $S(S(S(S(E))))<10$ we know that $S(S(S(S(2018^{2018}))))=4$

Joffan
  • 39,627
  • Thanks for the answer, it is quite similar to the answer by @fleablood. I've already estimated that the answer has to be less than 10 by calculating logarithms. I like your estimate better, since it does not require logarithm calculations. – Mikhail Genkin Dec 04 '17 at 23:43