8
$\begingroup$

I am not sure if this question is best suited for math exchange. I already tried on stackoverflow without any luck, so I hope that your bright minds will be more helpful.

So, basically the tile says everything. The numbers are not too big (so, this probably is not very interesting for the regular crowd here :)). The maximum for M is 2 * 10 ^ 63 and N is ~0.61 * M.

I made a small program for testing purposes that starts from N + 1, performs a simple Euclidean GCD, and if numbers are not relative primes we increment N.

I would like to know, is there any better solution. This looks very trivial, and maybe will be fast enough, but I would like to know is there anything better.

Also, if an answer for aforementioned question is No, I would like to know what is the worst case for the given algorithm.

I ran a test that will perform the above-described algorithm on some random numbers, and so far the result is always found in the less than 30 iterations.

Thanks.

  • 0
    Something 'not much more than N' would suite me just fine.2012-02-01

1 Answers 1

3

The number of positive integers smaller than $M$ and relatively prime to $M$ is given by Euler's totient function $\varphi(M)$. The following inequality holds for all $M>2$: $ \varphi(M)>\frac{M}{e^\gamma\log\log M+\frac{3}{\log\log M}},\quad e^\gamma=1.7810\dots $ On average, your algorithm should find the solution in at most $e^\gamma\log\log N$ iterations.

To speed the calculations, you could find a few small primes $p$ dividing $M$, and perform the Euclidean MCD only on candidates that are not divisible by those primes. For instance, if $M$ is even, you should try only odd candidates. This will be most helpful if you have to do the computations for a fixed $M$ and many different $N$'s.

  • 0
    @TonyK That the expected value of the number of iterations needed is $e^\gamma\log\log N$, that is, between $N+1$ and $N+e^\gamma\log\log N$, unless you are unlucky, there should be an integer relatively prime to $M$. This is a heuristic and probabilistic argument.2012-02-01