How Many Times Can You Add Up the Digits?

For a positive whole number $N$, let $f(N)$ be the number of times you must add up its digits before you reach a one-digit number. For example, $f(23) = 1$, since $2 + 3 = 5$, and $f(888) = 2$, since $8 + 8 + 8 = 24$ and then $2 + 4 = 6$. Find the smallest whole number $N$ with $f(N) = 4$.

The Fiddler, Zach Wissner-Gross, February 2, 2024(original post)

The official solution appeared in the post of February 9, 2024 and gives $2 \times 10^{22} - 1$, a one followed by twenty-two nines, for the main puzzle, agreeing with the answer below. The Extra Credit half of that post is paywalled, so the count of $945$ is my own and has not been checked against it.

Solution

Write $s(N)$ for the sum of the digits of $N$. For a number with two or more digits, the first step replaces $N$ by $s(N)$, and the rest of the process is just the process for $s(N)$. So $$f(N) = 1 + f\bigl(s(N)\bigr) \qquad\text{for } N \ge 10 .$$ To have $f(N) = 4$, the digit sum $s(N)$ must have $f = 3$. So build up the smallest numbers with each value of $f$, one level at a time.

• $f(N) = 0$ means $N$ already has one digit: $1, 2, \dots, 9$.

• $f(N) = 1$ means $N \ge 10$ with digit sum below $10$. The smallest is $10$.

• $f(N) = 2$ means $N$’s digit sum has $f = 1$, so it is at least $10$. The smallest number with digit sum $10$ is $19$, and indeed $1 + 9 = 10$, then $1 + 0 = 1$.

• $f(N) = 3$ means $N$’s digit sum has $f = 2$. Looking at the numbers with $f = 2$, they are $19, 28, 29, 37, 38, 39, \dots$, so the digit sum must be at least $19$. The smallest number with digit sum $19$ is $199$.

Now the step that matters. If $f(N) = 4$, then $f(s(N)) = 3$, and every number with $f = 3$ is at least $199$, as just shown. So the digits of $N$ add up to at least $199$. Each digit is at most $9$, and $22 \times 9 = 198$, so $N$ needs at least $23$ digits. The smallest $23$-digit candidate starts with a $1$, and then its other $22$ digits must supply at least $198$, which forces them all to be $9$. That number is $$N = 1\underbrace{99\ldots9}_{22 \text{ nines}} = 2 \times 10^{22} - 1 ,$$ and it works: its digit sum is $1 + 22 \times 9 = 199$, and $199 \to 19 \to 10 \to 1$ takes three more steps. $$\boxed{\ N = 2 \times 10^{22} - 1 = 19{,}999{,}999{,}999{,}999{,}999{,}999{,}999. \ }$$ The same climb gives the next record. The smallest $N$ with $f(N) = 5$ has digit sum $2 \times 10^{22} - 1$, so it is a $1$ followed by $(2 \times 10^{22} - 2)/9$ nines, about $2.2 \times 10^{21}$ of them.

The computation

The program applies the definition directly. It finds by search the smallest number with each value of $f$ up to $3$, confirms that no digit sum below $199$ has $f = 3$, and checks the answer.

def f(n):
    steps = 0
    while n >= 10:
        n = sum(map(int, str(n)))
        steps += 1
    return steps

for k in range(4):
    print(f"smallest with f = {k}:",
          next(n for n in range(1, 10**4) if f(n) == k))

N = 2 * 10**22 - 1
print("N =", N, " f(N) =", f(N), " digits:", len(str(N)))

It prints

smallest with f = 0: 1
smallest with f = 1: 10
smallest with f = 2: 19
smallest with f = 3: 199
N = 19999999999999999999999  f(N) = 4  digits: 23

Because the smallest number with $f = 3$ is $199$, any $N$ with $f(N) = 4$ needs digit sum at least $199$ and so at least $23$ digits, and the printed $N$ is the smallest such $23$-digit number.

Extra Credit

For how many whole numbers $N$ from $1$ to $10{,}000$ is $f(N) = 3$?

Solution

The number $10{,}000$ has digit sum $1$, so $f = 1$ and it does not count. Every other $N$ in range has at most four digits, so its digit sum is at most $36$. We need $f(s(N)) = 2$. Among $1$ to $36$, the numbers with $f = 2$ are those whose digits add up to $10$ or more: $19$, $28$ and $29$ (the next, $37$, is too big). So we must count the four-digit strings $d_1 d_2 d_3 d_4$ (leading zeros allowed, since they do not change the digit sum) with digit sum $19$, $28$ or $29$.

Counting strings of four digits with a given sum is a stars-and-bars problem with a cap of $9$ on each digit. Without the cap, the number of ways to write $s = d_1 + d_2 + d_3 + d_4$ with each $d_i \ge 0$ is $\binom{s + 3}{3}$. A string in which some digit is $10$ or more can be counted by taking $10$ off that digit, so inclusion and exclusion gives $$c(s) = \binom{s+3}{3} - 4\binom{s-7}{3} + 6\binom{s-17}{3} - \cdots,$$ with terms dropping out once the top number is below $3$.

• For $s = 19$: $c = \binom{22}{3} - 4\binom{12}{3} = 1540 - 880 = 660$.

• For $s = 28$ and $29$, replace each digit $d$ by $9 - d$. This turns digit sum $s$ into $36 - s$, one for one, so $c(28) = c(8) = \binom{11}{3} = 165$ and $c(29) = c(7) = \binom{10}{3} = 120$.

Adding, $$\boxed{\ 660 + 165 + 120 \;=\; 945 \text{ numbers}. \ }$$

The computation

With the function $f$ from The computation above, simply count.

print(sum(1 for n in range(1, 10_001) if f(n) == 3))

It prints

945