Finding a first number greater than N, which is a relative prime number M

Question

Basically, the title says it all. The numbers are not too large (the maximum for N is ~ 2/3 * max (long), and max M is max (long)), so I think that even the simple solution that I have now is enough. M is always greater than N.

I currently have:

• The easiest one, just start with N + 1, do the usual Euclidean GCD, and if it returns 1, we will end, if we do not increase it and try again.

I would like to know what is the worst option with this solution. Performance is not a big issue, but still I feel that there should be a better way.

Thanks.

In the worst case, I did a little test:

Random r = new Random(); while (true) { long num = (long) r.Next(); num *= r.Next(); f((long)(num * 0.61), num); } ... public static int max; public static int f(long N, long M) { int iter = 0; while (GCD(N++, M) != 1) { iter++; } if (iter > max) { max = iter; Console.WriteLine(max); } return 0; } 

It runs for ~ 30 minutes, and in the worst case, 29 iterations. Therefore, I believe that there is a more accurate answer than O (N).

Answer 1

I don’t know the worst case scenario, but using the fact that M <2 ^64, I can link it higher with 292 iterations and lower by 53 (except for the restriction that the N / M ratio is approximately fixed).

Let p ₁ , ..., p _k be primes greater than or equal to 5 by which M is divisible. Let N '≥ N be the smallest integer such that N' = 1 mod 6 or N '= 5 mod 6. For each i = 1, ..., k, the prime p _i divides the maximum maximum (49 / p _i ) integers N ', N' + 6, N '+ 12, ..., N' + 288. The upper bound on Σ _{i = 1, ..., k} ceil (49 / p _i ) is Σ _{i = 3 , ..., 16} ceil (49 / q _i ) = 48, where q are primes starting from q ₁ = 2. (This follows from the fact that Π _{i = 3, ..., 17} ≥ 2 ⁶⁴ means that M is the product of no more than 14 different primes other than 2 and 3.) We conclude that at least one of the integers mentioned is mutually prime with M.

For a lower bound, let M = 614889782588491410 (the product of the first fifteen prime numbers) and let N = 1. After 1, the first integer, relatively prime with the first fifteen prime, is the sixteenth prime 53.

I expect both borders to be improved without much effort, although this is not clear to me. For the upper bound, handle separately the case when 2 and 3 are both divisors of M, since then M can be a product of at most 13 other prime numbers. For the lower bound, one could find a good M by running the Eratosthenes sieve to calculate for a whole series of integers of primes dividing these integers. Then expand the window over the entire range; if the product of individual strokes in the window is too large, advance the end of the back of the window; otherwise, advance the front end.

Answer 2

I am sure that this is not O (n). Knowing that spaces in prime numbers are log _e n, we can simply say that your algorithm has at most log _e n iterations (because after passing at most log _e n numbers you will see a new prime number that is paramount for your given n ) for more details about this space , you can see the space in the spaces .

So, for your limited case, it is less than log _e n = log _e 2 ⁶⁴ <= 44, and it will be less than 44 iterations.