IL-GILLIS 2016 Problem 3

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$ .

[list=a] [] 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$ . [/list]