Problem

Source: Israel National Olympiad 2016 Q3

Tags: sum of digits, number theory, Digits, modular arithmetic, digit sum



Denote by $S(n)$ the sum of digits of $n$. Given a positive integer $N$, we consider the following process: We take the sum of digits $S(N)$, then take its sum of digits $S(S(N))$, then its sum of digits $S(S(S(N)))$... We continue this until we are left with a one-digit number. We call the number of times we had to activate $S(\cdot)$ the depth of $N$. For example, the depth of 49 is 2, since $S(49)=13\rightarrow S(13)=4$, and the depth of 45 is 1, since $S(45)=9$. Prove that every positive integer $N$ has a finite depth, that is, at some point of the process we get a one-digit number. Define $x(n)$ to be the minimal positive integer with depth $n$. Find the residue of $x(5776)\mod 6$. Find the residue of $x(5776)-x(5708)\mod 2016$.