Number of $n \to p \bmod n$ before getting to 0

Question

There isn't much background context, but is there any estimations on how many iterations of $n \to p\% n$ are needed before $n$ becomes 0? Percentage sign is modulo. ($p$ is fixed, prime in my context but not sure if it matters).

For example, when $p=10^9+7$, the maximum number of iterations needed is $50$. When $p=998244353$ (a common prime in competitive programming) the number of iterations is $45$. I don't see any proof that it requires approximately $\log p$, but it seems like so.

Thank you for your time and help.

Answer 1

Let us remove the constraint that $p$ is a prime number. Given a strictly decreasing sequence $1=a_0 < a_1 < \ldots < a_k$ and consider the set

$$ S(\textbf{a}) := \{p: p \equiv a_j \pmod{a_{j+1}} \ \ \forall j = 0 \ldots k-1\} $$

This is exactly the set of numbers that will produce the sequence $\textbf{a}$ during this process. Note that this set is stable for shifting by $\text{lcm }\{ a_1, \ldots, a_k\}$, and that the set of solutions is determined by applying the chinese remainder theorem.

We will consider two particular sequences to get the following result: (1) there exist arbitrarily large (prime) numbers that ends in $2$ iterations; (2) there exist arbitrarily large numbers that ends in at least (about) $(\log p) /2 $ iterations.

For the first just consider the sequence $3>1$ and take a (prime) number $p\equiv 1 \pmod{3}$.

The second is more interesting. Consider the sequence $k > \ldots > 1$. This means that we have $p$ such that $p\equiv m-1 \equiv -1 \pmod{m}$ for all $m\le k$. Solutions of this system are exactly numbers that are $\equiv -1$ modulo $L_k:= \text{lcm}\{1, \ldots, k\}$. The smallest such positive number is exactly $L_k -1$. We can give an estimate of $\log L_k$ as starting from the equation

$$ L_k = \prod_{p \le k} p^{[\log k/\log p]}$$

Indeed, any prime will appear with the maximum exponent it can appear with. Taking the logarithm we get

$$ \log L_k = \sum_{p\le k} (\log p) [\log_p k] \le \sum_{p \le k} (\log p) (\log_p k +1) $$ $$ = \sum_{p\le k} \log k + \log p \le \sum_{p\le k} 2 \log k \approx (2 \log k) \frac{k}{\log k} = 2k $$

Using the prime counting theorem $|\{p\le k\}| \approx k/\log k$. Recall that $k$ is the number of iterations relative to the input number $p=L_k-1$. Thus we get $$( \log p )/2 \approx ( \log L_k)/2 < k$$

Giving the desired solution.

Answer 2

Here's a semi-logarithmic plot of the maximum number of iterations required for a given $p$, with $p$ ranging from 5 to 5000, checking all $2 \le n < p-1$. Both the best & worst cases do seem to be growing logarithmically.

And here's a plot of the mean number of iterations, for $1 \le n < p$.

These plots were produced using Sage / Python. You can play with an online interactive version here (the script is actually encoded in the URL, not stored on the server). If you set the 'hi' parameter too high, the server will probably time out.