3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Since the algorithm always returns 0, what would be the application of such a computation? $\endgroup$
    – Hank Igoe
    Jan 3, 2023 at 12:50
  • 1
    $\begingroup$ @HankIgoe: counting the iterations ? $\endgroup$
    – user16034
    Jan 3, 2023 at 17:06

2 Answers 2

2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ How can you construct such an $M$ ? $\endgroup$
    – user16034
    Jan 5, 2023 at 9:25
  • $\begingroup$ @YvesDaoust I posted such a construction (though that didn't really answer OP's question, but I didn't really could post it as a comment). $\endgroup$
    – Nathaniel
    Jan 5, 2023 at 11:46
  • $\begingroup$ For $n = 4$, $m=11 < 4!-1$ is enough (see my answer). $\endgroup$
    – Nathaniel
    Jan 5, 2023 at 12:47
  • $\begingroup$ @Nathaniel, you are right of course. It should be the least common multiple of 1 to n, minus 1. $\endgroup$
    – gnasher729
    Jan 5, 2023 at 13:28
  • $\begingroup$ @gnasher729 yes, that's what I wrote in my answer. $\endgroup$
    – Nathaniel
    Jan 5, 2023 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.