# Digit sum of a huge number

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

• 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^{3*672 + 2}\equiv (-1)^{672}*2^2\equiv 4 \mod 9$. So the answer is$4$. Dec 4, 2017 at 23:17 ## 2 Answers 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$. • Wow, thanks! I got it. Turns out to be quite challenging problem Dec 4, 2017 at 23:35 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\$

• 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. Dec 4, 2017 at 23:43