- #1
ppnl
- 37
- 0
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 said:
ppnl said: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.
ppnl said: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 said:Ooooooooh! I think I finally get what you meant! You actually wanted to ask: given the first n primes [itex]\,p_1,...,p_n\,[/itex] , what is the maximal possible difference of the form
[itex]\,a-b\,[/itex] , [itex]\,a>b\,\,,\,\,and\,\,\,\forall\,k\,\,,\,a<k<b\,\,\,\,\,p_j\mid k\,\,\,,\,\,\text{for some}\,\,1\leq j\leq n\,\,?[/itex]
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.robert2734 said: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 said: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.
N=4 P,2,5,2,3,2,5,2,7,2,3,2,5,2,P
robert2734 said: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.
Relative prime gaps refer to the differences between consecutive numbers that have no common factors besides 1. For example, the numbers 3 and 5 have a relative prime gap of 2, while the numbers 8 and 10 have a relative prime gap of 2 as well, even though their absolute difference is 2.
The study of relative prime gaps is important in number theory and cryptography. A fast algorithm for calculating these gaps can greatly improve the efficiency of these fields, allowing for more complex calculations and faster analysis of data.
The algorithm uses a combination of sieving and pre-computed values to efficiently determine the relative prime gaps between a given range of numbers. It first sieves out all numbers with small prime factors, then uses pre-computed data to quickly check for larger prime factors. This results in a highly optimized and fast algorithm for calculating relative prime gaps.
This algorithm can be used in various fields such as number theory, cryptography, and data analysis. It can help in identifying patterns and trends in data, as well as improving the efficiency of encryption and decryption methods in cryptography.
Like any algorithm, there are limitations to the speed and accuracy of this method. It may not be able to efficiently calculate relative prime gaps for extremely large numbers, and there may also be potential for errors in the pre-computed data used. Further research and improvements can help overcome these limitations.