Disclaimer: This is a past programming problem, but I'm asking for some mathematical insights and proofs.
Consider a function $sum\_digits(n)$ which computes the sum of digits of a number. Then, a function $iterations(n)$ is the number of repeated application of $sum\_digits(n)$ until the values becomes 1-digit.
For all 1-digit numbers (i.e [0, 9]) $iterations(x) = 0$.
Further examples:
iterations(10) = 1
iterations(19) = 2
iterations(299) = 3
iterations(2999) = 4
Now, consider a function $min\_number(x)$ which computes the minimum non-negative integer n such that $iterations(n) = x$.
I am interested in the first 7 values modulo some integer $M$ where $1 \le M \le 2e7$. The modulo is necessary, because the last two answers are two huge to fit in memory or print.
The first 4 values are:
min_number(0) = 0
min_number(1) = 10
min_number(2) = 19
min_number(3) = 199
min_number(4) = 19999999999999999999999
min_number(5) = ?
min_number(6) = ?
By observation, $min\_number(x)$ can be computed based on $min\_number(x – 1)$ as follows:
$min\_number(x) = 2 * 10^{\frac{min\_number(x – 1) – 1}{9}} – 1$
I want to compute it fast enough, so I've taken a look at some ways to reduce the problem. I have read about Euler's Theorem, Chinese Remainder Theorem (CRT) and Modular Inverses. They provide some significant steps but I have a few roadblocks.
Euler's Theorem is applicable to the power by applying mod $φ(M)$ where φ is Euler's totient function. However, I am constrained by the limitation that the base and modulo are co-prime (i.e. gcd is 1). In this case, the base is 10 and the modulo can share a factor with the modulo M.
1. Case $\gcd(10, M) = 1$
Direct application to Euler's Theorem. But leads to two more cases when applying the power.
1.1 Case $\gcd(φ(M), 9) = 1$
Get the modulo inverse of 9 by Extended Euclid, so that division by 9 can be done.
1.2 Case $\gcd(φ(M), 9) \ne 1$
Roadblock because modular inverse doesn't exist.
2. Case $\gcd(10, M) \ne 1$
Produce three moduli from M: $2^i$ and $5^j$ and $\frac{M}{2^{i}5^{j}}$ where $2^i$ and $5^j$ are the largest powers that divide M. Apply CRT to get back the result modulo M.
For the first two modulo, the answer is always $2^0 – 1 = -1$ for n > 4, because the exponent is large enough. For the third modulo, we can apply Euler's theorem.
Let m = $\frac{M}{2^{i}5^{j}}$
2.1 Case $φ(m, 9) = 1$
Same as Case 1.1.
2.2 Case $φ(m, 9) \ne 1$
Road block. Same as Case 1.2.
I'm looking for an algorithm that solves all cases.
Best Answer
Making a new answer since my first answer was from a misunderstanding of the question.
We can compute the problem modulo any reasonably small $M$ using a recursive algorithm as follows. I'll use the (in my opinion) simpler notation $m_n$ for what you've defined as $min\_number(x)$, and I'll define $a_n = (m_n-1)/9$. The goal will be to compute $a_n$ modulo $M$, since $m_n$ can be trivially recovered from $a_n$.
First note that using the Chinese remainder theorem, we can always assume that $M = p^\ell$ is a prime power.
Now first suppose $p\neq 2,3,5$. Then we can recursively compute $a_{n-1}\mod \phi(M)$, and since $9$ is invertible mod $M$ we can compute $a_n\equiv 9^{-1}\cdot (2\cdot10^{a_{n-1}\mod\phi(M)}-2)\mod M$.
Now suppose $p=2$ or $p=5$. I'll make the basic assumption that $\ell < (m_4-1)/9$. Note that $\ell$ is basically the log of $M$, so this is hardly an assumption. But looking at the recursive formula, clearly if $M=2^\ell$ or $M=5^\ell$ with $\ell < (m_4-1)/9$, then $m_n \equiv -1\mod M$ for all $n>4$. Again since we have a modular inverse for $9$ mod $M$, we can compute $a_n \equiv -2\cdot 9^{-1}\mod M$ for $n>4$.
Finally we consider $p=3$. Now to compute $a_n$ modulo $3^\ell$, it suffices to compute $m_n$ modulo $3^{\ell+2}$; indeed, suppose $3^{\ell+2} + k = m_n = 9a_n+1$. Then subtracting one from both sides and dividing by $9$, we get $3^{\ell} + (k-1)/9 = a_n$, i.e. $a_n \equiv (k-1)/9 \mod 3^{\ell}$ iff $m_n\equiv k \mod 3^{\ell+2}$.
Now we can recursively compute $a_{n-1}\mod \phi\left(3^{\ell+2}\right)$, and derive $m_n\equiv 2\cdot10^{a_{n-1}\mod\phi\left(3^{\ell+2}\right)}-1\mod 3^{\ell+2}$, and we're done.
Note that even though the CRT step branches the process, it only branches it into prime powers smaller than $M$. Thus if you simultaneously compute the values of $a_n$ for every prime power smaller than $M$, the complexity is actually bounded in time $O\left(\frac{M}{log(M)}n\right)$ (note that $\phi(3^\ell) = 2\cdot 3^{\ell-1}$, so even though $M$ gets bigger when it's a power of $3$, this only increases the number of values we need to compute by a term linear in $n$).