Euler Theorem and Modular Inverse for Non Coprime Problem

Question

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.

Answer 1

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$).

Answer 2

$M$ is not needed because we can derive a recursive formula for $min\_number(n)$ explicitly as follows (the recursive formula we derive is almost the same as the one you observed in your post; I assume the one you actually wrote is simply a typo).

First of all, suppose we know $m:=min\_number(n-1)$. Then $min\_number(n)$ is the smallest number $m'$ such that the sum of the digits of $m'$ is equal to $m$. Indeed, certainly we know $iterations(m') = n$. But for any number $k$ such that $iterations(k)=n$, we know by definition of $m$ that the sum of the digits of $k$ is at least $m$. Therefore after possibly making some of the digits smaller, we get a number $k'\leqslant k$ such that the digits of $k'$ sum to $m$. Then by definition of $m'$, we have $m'\leqslant k'\leqslant k$. Thus $m'$ must be the minimal number with $n$ iterations.

Now let $a_k,...,a_0$ be the ordered digits of $m'$, i.e., $m' = a_k\cdot10^k + ... + a_1\cdot10 + a_0$. If some digit $a_i$ is less than $9$, then we can always increase $a_i$ by one and decrease $a_{i+1}$ by one without changing the sum of the digits. Thus we must have $a_0,...,a_{k-1}$ all equal to $9$ since otherwise $m'$ would not be minimal.

We now prove by induction that $m' = 10^k + 9\cdot 10^{k-1} + ... + 90 + 9$ for some $k$ (we will derive $k$ explicitly later). You've already shown the base case, so we only need to prove the inductive part.

So by the inductive hypothesis we may assume $m = 10^l + 9\cdot 10^{l-1} + ... + 90 + 9$ for some $l$. All of the $9\cdot 10^i$ terms are divisible by $9$ and hence go to zero. Also $10\equiv 1\mod 9$ so $10^l\equiv 1\mod 9$. Combining these results, we get $m\equiv 1\mod 9$.

But we know from the second paragraph that the sum of the digits of $m'$ equals $m$, and we know from the third paragraph that except possibly $a_k$, all of these digits are equal to $9$. Thus $1\equiv m \equiv a_k + ... + a_0 \equiv a_k\mod 9$. Since $a_k\leqslant 9$, this shows in fact $a_k = 1$, i.e. $m' = 10^k + 9\cdot 10^{k-1}+...+9$ just like we wanted to show.

So we now know that $min\_number(n)$ can be written in the form $1999999...$, and all that remains is to figure out how many nines there are. We can find a recursive formula for this as follows.

First note that we have $10^l = 9\cdot\left(\frac{10^l-1}{9}\right) + 1$ and $10^{l-1}+...+1 = \frac{10^l-1}{9}$ for all $l$. Now if $m=min\_number(n-1)$ has $d_{n-1}$ nines, then $m=10^{d_{n-1}} + 9\cdot\left(10^{d_{n-1}-1}+...+1\right) = 9\cdot2\cdot\left(\frac{10^{d_{n-1}}-1}{9}\right)+1$. But the sum of the digits of $min\_number(n)$ is $9\cdot d_n+1$.

Thus we have $d_n = \frac{2}{9}\cdot(10^{d_{n-1}} - 1)$. You can check this formula holds for the values you've calculated.

Using $min\_number(n)=2\cdot\left(10^{d_n}-1\right)+1$, it's easy to show this is equivalent to $min\_number(n) = 2\cdot 10^{\frac{min\_number(n-1)-1}{9}}-1$.