How Many Times Can You Add Up the Digits?

Extra Credit

Switching it up this time because the extra credit is a bit easier!

10K is small enough that we can write a loop for it. A cheeky but inefficient-ish way in Python to sum the digits of N is sum(map(int, str(N))). We can list our trivial cases, the single-digit numbers mapping to 0, and for each N we see later, we take the sum of N's digits (call it n), find f(n), and add 1 to it to represent one step. Iterate up to and including 10000.

f = [0] * 10
while len(f) < 10001:
    N = len(f)
    n = sum(map(int, str(N)))
    f.append(1 + f[n])
print(f.count(3))

Output:

945

Technically, the solution is dynamic programming, but honestly, it's just the most straightforward way to write it. Brute force would also run instantly because the depth never exceeds 3 :)

Answer: 945

This Week's Fiddler

So running the program again but changing the stop condition to f[-1] == 4, the loop doesn't really stop. That's because the next number is really large, larger than my measley brute-force algorithm on my non-quantum computer can handle within the lifetime of the Sun.

Since we already calculated all $1\le N\le 10000$ where $f(N)=3$, we can find the smallest such $N$:

F.index(3)

Output:

199

Now we construct the smallest number whose digits add up to this!

To minimize the digits, we can stuff the least significant digits with 9s and put the remainder as the most significant digit. This works out to 22 "9"s preceded by a "1", or 19999999999999999999999.

We could have used this technique to construct from the number 10 upwards (to get 19 to get 199), but best use the resources available to you 😎

What about numbers beyond? Let $g(k)=N$, such that $N$ is the minimum $N$ satisfying $f(N)=k$. So $g(1)=10$, $g(2)=19$, $g(3)=199$, and $g(4)=19999999999999999999999$. Something to note is that modularity to 9 in base 10 is defined by the sum of digits, so building up from this sequence will never change the fact that $g(k) \equiv 1\ (\textrm{mod}\ 9)$ for $k>0$. As such, the leading digit will always be 1 and the rest of the digits 9.

How many 9s? Well that's a TODO for me later!

Answer: 19999999999999999999999