This week’s Fiddler is a puzzle about adding digits over and over again.

For any positive, base-10 integer $n$, define $f(n)$ as the number of times you have to add up its digits until you get a one-digit number. For example, $f(23) = 1$ because $2+3 = 5$, a one-digit number. Meanwhile, $f(888) = 2$, since $8+8+8 = 24$, a two-digit number, and then adding up those digits gives you $2+4 = 6$, a one-digit number. Find the smallest whole number $n$ such that $f(n) = 4$.

*Extra Credit:* For how many whole numbers $n$ between $1$ and $10,000$ does $f(n) = 3$?

My solution:

[Show Solution]

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.