How many times can you add up the digits?

Let $a_n$ be the smallest integer $n$ such that $f(a_n) = n$. We can calculate the first few values manually.

• $a_1 = 10$. This must be the case since every one-digit number has $f(n)=0$, and $10$ is the smallest two-digit number and $f(10)=1$.
• $a_2 = 19$. We seek the smallest number such that the sum of its digits needs to be summed once more to get to a one-digit number. In other words, we want the smallest number whose digits sum to $10$. This requires at least two digits and can be done in two ways ($19$ and $91$). Using more than two digits leads to larger numbers so we can exclude these possibilities.
• $a_3 = 199$. Now, we seek the smallest number whose digits sum to $19$. This is impossible with two digits (smallest sum is $9+9=18$), so we try with three. This can be done with a $1$ as the first digit ($1+9+9$), so this must be the answer.

The pattern is now clear. For all $n\geq 1$, $a_{n+1}$ is the smallest integer whose digits sum to $a_n$. Based on the pattern, let’s suppose that
\[
a_n = 1\,\underbrace{9\,9\,\cdots\,9}_{k_n\text{ times}}
\qquad\text{for }n=2,3,\dots
\]where $k_2=1$ and $k_3=2$. Now $a_{n+1}$ is the smallest number whose digits sum to $a_n$. How many digits must $a_n$ have? Rewrite $a_n$ in a particular way:
\begin{align}
a_n &= 1\,\underbrace{9\,9\,\cdots\,9}_{k_n\text{ times}}\\
&= 2\cdot 10^{k_n}-1 \\
&= 2\left( 10^{k_n}-1\right)+1 \\
&= 2\cdot 9\cdot \left( \frac{10^{k_n}-1}{10-1}\right)+1\\
&= 2\cdot 9\cdot \left( 1+10+10^2+\cdots+10^{k_n-1}\right) +1 \\
&= 9 \cdot \bigl(\, \underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}\,\bigr) + 1
\end{align}where we used the formula for a finite geometric series in the third step. Based on this representation, it is clear that $a_{n+1}$ requires more than $\underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}$ digits, since even if we made all the digits $9$ it would not be enough. W should add the extra $+1$ digit at the front of the number to get the smallest number possible. This leads to:
\[
a_{n+1} = 1\underbrace{9\,9\,\cdots\,9}_{\underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}\text{ times}}
\]So $a_{n+1}$ is of the same form as $a_n$, and we find:
\[
k_{n+1} = \underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}\qquad\text{for }k=2,3,\dots.
\]So although the sequence $f(n)$ seemed to grow at a moderate pace, for $n=0,1,2,3$, we find that
\[
f(4) = 19,\!999,\!999,\!999,\!999,\!999,\!999,\!999
\]That escalated quickly!

In general, we can write the full recursion as:
\begin{align}
a_1 &= 10,\\
a_2 &= 19,\\
a_{n+1} &= 2\cdot 10^{(a_n-1)/9}-1\qquad\text{for }n=2,3,\dots
\end{align}

Extra credit

The most straightforward way to count how many $n$ between $1$ and $10,\!000$ satisfy $f(n)=3$ is to write a short script. Here is a two-line script in Julia that does the job:

f(n) = n < 10 ? 0 : 1 + f(sum(digits(n)))
length( [n for n in 1:10000 if f(n) == 3] )

and the answer is 945.