How Many Times Can You Add Up the Digits?

Fiddler

From Tom Rich comes a short-ish puzzle with a long-ish answer:

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.

Solution

I looked at simpler problems first.

$f(N) = 0$

$N=1$ is the smallest value of $N$.

$f(N) = 1$

$10$ is the smallest number whose digits sum to $1$.

$f(N) = 2$

$19$ is the smallest number whose digits sum to $10$.

$f(N) = 3$

$199$ is the smallest number whose digits sum to $19$.

Answer

$f(N) = 4$

Using the pattern above, $19,999,999,999,999,999,999,999$ is the smallest number whose digits sum to $199$.

Extra Credit

Now that you’ve had some fun with larger numbers, let’s return to more mundane orders of magnitude.

For how many whole numbers N between 1 and 10,000 (inclusive, not that it matters) does f(N) = 3?

Solution

The maximum sum is $36$, from $9,999$. The values of $M \le 36$ such that $f(M) = 2$ are $M = 19, 28, 29$. From these values of $M$, calculate the number of ways to sum the digits of $N$ to achieve $M$, thus $f(N) = 3$.

$N = 19$

3-digit

The maximum sum of a 3 digit number is $999$. Subtracting 8 from the values of the digits in any manner will yield a sum of $19$. 8 'subtractions' to be placed among 3 digits can be represented as

$\dfrac{10!}{8!2!} = 45$

4-digit

I could not find a clean way to calculate this. Using code I found there are 615.

$N = 28$

Similar to 3-digit of $N=19$, calculate the number of ways to take away $8$ from the digits of $9999$.

$\dfrac{11!}{8!3!} = 165$

$N = 29$ min

Similar to 3-digit of $N=19$, and $N=28$ calculate the number of ways to take away $7$ from the digits of $9999$.

$\dfrac{10!}{7!3!} = 120$

Answer

$45+615+165+120 = 945$

Rohan Lewis

2024.02.05

Code can be found here.