Relative Prime Gaps: Fast Algorithm for Calc.

[ppnl]

Given the first N prime numbers what is the largest gap between consecutive numbers that are relatively prime to all of them? Anyone know of a fast algorithm for calculating this?

 

[coolul007]

http://number.subwiki.org/wiki/There_exist_arbitrarily_large_prime_gaps

 

[ppnl]

http://number.subwiki.org/wiki/There_exist_arbitrarily_large_prime_gaps

Yes I know that there are arbitrarily large prime gaps. I'm asking something different.

Again, given the first N primes, say 2,3,5,7 and 11, what is the largest gap between consecutive numbers not divisible by any of these? the answer for this (where N=5) is 14. I want a fast way to calculate this for any value of N.

 

[DonAntonio]

Yes I know that there are arbitrarily large prime gaps. I'm asking something different.

Again, given the first N primes, say 2,3,5,7 and 11, what is the largest gap between consecutive numbers not divisible by any of these? the answer for this (where N=5) is 14. I want a fast way to calculate this for any value of N.

It must be the global warming but I don't get it: for any integer \,k\, , any \,k\, consecutive integers will have exactly one

multiple of k (in fact, exactly one integer \,=i\pmod j\,\,\,,\,\,\forall i=0,1,2,...,k-1\, ), thus: any list of two (2) consecutive integers will

have exactly one element divisible by 2 , from where I can't understand how you came up with 14, and I gather then that you must be trying

to convey to us something different from what I am understanding...

DinAntonio

 

[ppnl]

Ok, let me try again.

What is the biggest gap between consecutive numbers not divisible by two? Obviously it is two. 3 and 5 for example are consecutive numbers not divisible by two. They are not consecutive integers but they are consecutive numbers not divisible by two. They are also consecutive primes despite not being consecutive integers. Two is the answer for N=1.

Now take the primes 2 and 3. What is the largest gap that can exist between consecutive numbers indivisible by 2 or 3? I don't mean consecutive integers here. I mean consecutive coprimes to 2 and 3. For example 7 and 11 are consecutive coprimes to 2 and 3. The answer for N=2 is 4.

And what is the maximum gap between consecutive numbers that are coprime to 2, 3 and 5? The answer is 6. For example 23 and 29 are consecutive coprimes to 2, 3 and 5 with a gap of 6 between them. The answer for N=3 is 6.


In the more general case given a random set of prime numbers what is the maximum gap between consecutive coprimes to that set of prime numbers?

 

[DonAntonio]

Ok, let me try again.

What is the biggest gap between consecutive numbers not divisible by two? Obviously it is two. 3 and 5 for example are consecutive numbers not divisible by two They are not consecutive integers but they are consecutive numbers not divisible by two. They are also consecutive primes despite not being consecutive integers. Two is the answer for N=1
Now take the primes 2 and 3. What is the largest gap that can exist between consecutive numbers indivisible by 2 or 3? I don't mean consecutive integers here. I mean consecutive coprimes to 2 and 3. For example 7 and 11 are consecutive coprimes to 2 and 3. The answer for N=2 is 4.

And what is the maximum gap between consecutive numbers that are coprime to 2, 3 and 5? The answer is 6. For example 23 and 29 are consecutive coprimes to 2, 3 and 5 with a gap of 6 between them. The answer for N=3 is 6. .

Ooooooooh! I think I finally get what you meant! You actually wanted to ask: given the first n primes \,p_1,...,p_n\, , what is the maximal possible difference of the form

\,a-b\, , \,a>b\,\,,\,\,and\,\,\,\forall\,k\,\,,\,a<k<b\,\,\,\,\,p_j\mid k\,\,\,,\,\,\text{for some}\,\,1\leq j\leq n\,\,?

In the more general case given a random set of prime numbers what is the maximum gap between consecutive coprimes to that set of prime numbers?

Ok, now I understood but I've no idea about your question. In case of first consecutive primes the answer is always an even

number, obviously, and perhaps easier to calculate than taking a random set of primes, which seems to make this a hopeless question...but who knows?

DonAntonio

 

[ppnl]

Ooooooooh! I think I finally get what you meant! You actually wanted to ask: given the first n primes \,p_1,...,p_n\, , what is the maximal possible difference of the form

\,a-b\, , \,a>b\,\,,\,\,and\,\,\,\forall\,k\,\,,\,a<k<b\,\,\,\,\,p_j\mid k\,\,\,,\,\,\text{for some}\,\,1\leq j\leq n\,\,?

Yes I think that's it but it really obscures what is going on. Just do a sieve of Eratosthenes using only the first N primes and find the largest relative prime gap that it leaves. But this method of finding the gaps is very slow.

There is another method using permutations of the prime list but it is a mess for me to program.

I know there has been a lot of work on prime gaps. I was just wondering if anyone had considered relative prime gaps.

 

[robert2734]

Let Xn be the product of the first n primes. Let Pn+1 be the n+1th prime. Let k be any positive integer. Then kXn+2 to kXn+(Pn+1)-1 are all multiples of at least one of the first n primes. Also kXn-2 to kXn-(Pn+1)+1 is also a prime gap of the same size. I would conjecture they are the largest prime gap.

Note that your prime gap function is symetric around Xn(k+1/2). And periodic with period Xn.

 

[ramsey2879]

Let Xn be the product of the first n primes. Let Pn+1 be the n+1th prime. Let k be any positive integer. Then kXn+2 to kXn+(Pn+1)-1 are all multiples of at least one of the first n primes. Also kXn-2 to kXn-(Pn+1)+1 is also a prime gap of the same size. I would conjecture they are the largest prime gap.

Note that your prime gap function is symetric around Xn(k+1/2). And periodic with period Xn.

Actually, there can be a larger gap than that! For example, the first 5 primes are 2,3,5,7,11 and the prime gap can be as large as 14. Let a be the prior prime and a + 14 be the next prime. The 13 number gap between these two primes can be filled with numbers divisible respectively by 6,5,2,3,2,7,30,11,2,3,2,5,42. As can be seen each is a product of one or more of the first 5 primes. 14 is a larger number than the 6th prime.

 

[ppnl]

Actually, there can be a larger gap than that! For example, the first 5 primes are 2,3,5,7,11 and the prime gap can be as large as 14. Let a be the prior prime and a + 14 be the next prime. The 13 number gap between these two primes can be filled with numbers divisible respectively by 6,5,2,3,2,7,30,11,2,3,2,5,42. As can be seen each is a product of one or more of the first 5 primes. 14 is a larger number than the 6th prime.

Now we are getting somewhere.

It is easy to show that the max gap for the first N prime numbers is at least two times the N-1th prime. We can always construct a gap of exactly this size. We construct the gap by listing the smallest prime a position in the gap is divisible by like this:



N=3 P,2,3,2,5,2,P
N=4 P,2,5,2,3,2,5,2,7,2,3,2,5,2,P
N=5 P,2,3,2,7,2,5,2,3,2,7,2,11,2,3,2,5,2,7,2,3,2,P

See the pattern? If so you can easily see that this gap always exists, is equal to two times the N-1th prime and there are exactly two of them. But is this always the largest gap? That would be a beautiful result if you could prove it. It is true for n=1,2,3,4,5,6,7 and 8.

But it fails for N=9. I would like to know if it fails for an infinite number of cases, how often it fails and some idea of the conditions that cause it to fail. So far it seems the failures are rare but I'm limited on how far I can compute the gaps.

 

[robert2734]

N=4 P,2,5,2,3,2,5,2,7,2,3,2,5,2,P

Your middle 5 is four away from the first 5 and six away from the last 5. That doesn't happen.
Following my algorithm for N=4, 2*3*5*7=210 and 212 to 220 is a prime gap. 200 to 208 is also a prime gap. 221 is actually 13*17 and 209 is 11*19 but neither is a multiple of 2,3,5 or 7.

N=4 P,2,3,2,5,2,7,2,3,2,P. You can't do better.

In your example for N=5, the 7's are shifted.

 

[ppnl]

Your middle 5 is four away from the first 5 and six away from the last 5. That doesn't happen.
Following my algorithm for N=4, 2*3*5*7=210 and 212 to 220 is a prime gap. 200 to 208 is also a prime gap. 221 is actually 13*17 and 209 is 11*19 but neither is a multiple of 2,3,5 or 7.

N=4 P,2,3,2,5,2,7,2,3,2,P. You can't do better.

In your example for N=5, the 7's are shifted.

OOPS! Sorry, my bad. That should be:

N=3--- P,2,3,2,5,2,P=2*3
N=4--- P,2,3,2,5,2,7,2,3,2,P=2*5
N=5--- P,2,5,2,3,2,7,2,11,2,3,2,5,2,P=2*7

To construct this gap we place the two largest primes in the middle with a two between:

...17,2,19...

Now going to the right we number the positions starting with 2:

...17,2,19,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

Then we reduce these numbers to the smallest prime that divides them:

...17,2,19,2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,P

Then we reflect to the left side:

P,2,3,2,13,2,11,2,3,2,7,2,5,2,3,2,17,2,19,2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,P

Clearly a gap with this pattern always exists, you can get two of them by swapping the center big primes and for small N at least it is often the largest gap.

 

[robert2734]

Yes. Your construction is better than mine. For N=5, 120=2x3x5, 119=7x, and 121=11x. So from 114 to 126 it is 2,5,2,3,2,7,2,11,2,3,2,5,2. A gap of 13. I only got a gap of 11 from 2312 to 2322 2,3,2,5,2,7,2,3,2,11,2.

For N=6 we have 210=2x3x5x7. 209=11x. But 211 isn't a multiple of 13. So we add 2310 to 211 and try again. Eventually we find 4*2310+211 is a multiple of 13. So we have from 9440 to 9460 2,3,2,7,2,5,2,3,2,11,2,13,2,3,2,5,2,7,2,3,2 a gap of 21.

 

[ppnl]

And for N=7 we get a gap of 2*13=26 as expected and with N=8 we get 2*17=34 as expected.

But for N=9 we expect a maximum gap of 2*19=38. A gap of that size does exist but we have a larger gap with of 40 with an irregular structure:

P,2,3,2,5,2,11,2,3,2,13,2,23,2,3,2,7,2,19,2,3,2,17,2,5,2,3,2,11,2,7,2,3,2,5,2,13,2,3,2,P

At N=10 and 11 we again have the expected 2*23=46 and 2*29=58 as maximum gaps. But at N=12 we again have a larger than expected maximum gap of 66 again with an irregular structure.

Calculating past this gets difficult unless I improve my algorithm.