Recursive Digit Sum

The recursive formula looks frustrating, but by deeply analyzing it, the point of the formula is that the next term of the sequence can be obtained by adding the digits of the previous term . For instance, let $n=63859$ Then $n_1=S(n)=6+3+8+5+9=31$ , $n_2=S(n_1)=3+1=4$ and so on.

Now, for this problem, we are asked for the number of $n$ whose one term in ${n_k}$ by the recursive formula is 9, that is, there is one time that the sum of the digits of the previous term is 9. Recall the divisibility rule of 9: A number is divisible by 9 if and only if the sum of its digits is also divisible by 9. Therefore, it follows that to get a 9 in the sequence, $n$ must be divisible by 9, and the number of integers $n$ divisible by 9 is

$\left \lfloor \frac{2013}{9} \right \rfloor = \boxed{223}$ .

In order to get the digit sum of 9, the sum must be wither 9, 18, or 27. Since we have maximum number in the given which is a four-digit number, the maximum digit is 28 and the minimum is 1.

The answer is simple. We can find such numbers which are simply divisible by 9. Hence, there are 223 numbers from 9 to 2007 inclusive.

First let's consider the general decimal representation of an $n$ -digit positive integer...

$\sum_{i=0}^{n} a_{i+1}10^i ~~~~~~~~~~~~~~ \text{Digit sum:} ~~~ \sum_{i=0}^{n}a_{i+1}$

$\text{Since}~~~~~~\sum_{i=0}^{n} a_{i+1}10^i\equiv \sum_{i=0}^{n}a_{i+1}\pmod{9}$

$\text{So if}~~~~~~~ \sum_{i=0}^{n}a_{i+1}\equiv 0 \pmod{9}$

$\text{Then}~~~~~~~~~~~ \sum_{i=0}^{n} a_{i+1}10^i\equiv 0 \pmod{9}$

Thus, for the digit sum of a positive integer to be divisible by $9$ , the number itself must be divisible by $9$ . And thus we can also see that according to the recurrence relation given in the question, the digit sum of all the positive integers divisible by $9$ will eventually become $9$ .

Hence, the answer is simply...

$\left\lfloor \dfrac{2013}{9}\right\rfloor = \fbox{233}$

On observing the sequence of numbers whose sum of digits give 9. we get the following numbers- 9,18,27,36,45..........so on. As these numbers are multiples of 9. Just divide 2013 by 9 and the quotient is the answer.

2013%9=6 2013-6=2007 2007/9=223