Complexity of taking recursive modulo

Given 2 integer $M$ and $N$, a recursive modulo is $M \bmod (M \bmod (M \bmod ...(M \bmod N)$ until the result is 0. What is its time complexity?

I guess that it's $O(log(M))$ but I can't prove it.

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

StackExchange Computer Science Q#156542, answer score: 2