Complexity of taking recursive modulo

Extending on @gnasher729's answer, I tried to find, given $N\in \mathbb{N}$, what is the smallest $M$ such that $N$ iterations of modulo are necessary before getting $0$ (and even finding if such an $M$ existed).

What we want to find is the smallest $M$ such that $\forall k\in \{1, …, N\}$, $M \equiv -1 \mod k$. Denote $f(N)$ such an $M$.

A few lines in Python after that, I found the following values:

• $f(2) = 1$;
• $f(3) = 5$;
• $f(4) = 11$;
• $f(5) = f(6) = 59$;
• $f(7) = 419$;
• $f(8) = 839$;
• $f(9) = f(10) = 2519$;
• $f(11) = f(12) = 27719$;
• $f(13) = f(14) = f(15) = 360359$.

Given those observations, I conjectured that the following algorithm could compute $f(N)$:

• $f(2) = 1$;
• if $N > 2$, then
  • either $N = p^{\alpha}$ with $p$ prime, and $f(N) = p\times (f(N-1) + 1) - 1$;
  • or $f(N) = f(N-1)$.

After a bit of search, I found out that I just rediscovered a formula to compute $\text{lcm}(1, 2, …, N) - 1$.

Given the definition of the least common multiple, it is clear that $f(N) \equiv -1 \mod k$ for all $k\in \{1, …, N\}$.

$f(N)$ is indeed the smallest such $M$: assume $M<\text{lcm}(1, 2, …, N) - 1$. Then there exists $k\in \{1, …, N\}$ such that $k \not\mid M + 1$. That means that $M\not\equiv -1\mod k$.

It’s obviously O(n) since the first modulo gives a result from 0 to N-1, then 0 to N-2, and so on. You can also construct m so that n steps are indeed needed. However, such an m could be very large, so the size of m will also limit this. (m = LCM(1..n) - 1 seems to be the smallest such number, so the number of steps can be n only if m ≥ LCM(1..n) - 1.)

For random x, the result of x mod n is (n-1)/2 on average, so the expected number of iterations would be log2(n).

For any m, n = m gives one iteration, and n > m gives two iterations. If n < m, then for m-1 ≥ n ≥ floor(m/2) + 1 we get all values from 1 to m - floor(m/2) - 1 after the first iteration.

For m < 100,000, the worst case is m = 93,596 and n = 33,851 where n = (93596 modulo n) goes through the sequence 25,894, 15,914, 14,026, 9,440, 8,636, 7,236, 6,764, 5,664, 2,972, 1,464, 1,364, 844, 756, 608, 572, 360, 356, 324, 284, 160, 156, 152, 116, 100, 96, 92, 32, 28, 20, 16, 12, 8, 4, 0. This is 34 iterations or 2.26 * log2(n). It is also the first record holder with even m. For m < 1,000,000, the worst case is m = 830,939 and n = 226,858 with 42 iterations.

So it seems that the worst case number of iterations grows at a small multiple of log_2 (m), with some n not far from m, and the values m modulo n around maybe 3/4 n instead of n/2. The case of having results modulo n of n-1, n-2, n-3 etc. is just too rare.