The first version of this post was written in 2016. I recently rewrote to make it more comprehensive.
As far as I know, there are a number of algorithms to determine whether a number is prime. This post is about determining the Gap that directly leads to the next prime number when a prime number and all smaller prime numbers are known. The procedure is deterministic. The next number found using this procedure will definitely be a prime. Matter of fact, this method works even if you start with any odd number, not necessarily a prime. The only requirement is that you need to have all pedigree info, i.e., all smaller prime numbers - right upto 3.
This post determine Gap (to find the next prime) for a given known prime. This is done by evaluating something called R1 for the current prime number. The difference between two successive prime numbers is called Gap. As per Oppermann's Conjecture. the gap size would be on the order of
. This post is about estimating the Gap and not about the Conjecture per se.
Read also the Table "80 known maximal prime gaps" https://en.wikipedia.org/wiki/Prime_gap. We will come back to Gap later in this post.
Let's start with the prime number 67
As far as I know, there are a number of algorithms to determine whether a number is prime. This post is about determining the Gap that directly leads to the next prime number when a prime number and all smaller prime numbers are known. The procedure is deterministic. The next number found using this procedure will definitely be a prime. Matter of fact, this method works even if you start with any odd number, not necessarily a prime. The only requirement is that you need to have all pedigree info, i.e., all smaller prime numbers - right upto 3.
This post determine Gap (to find the next prime) for a given known prime. This is done by evaluating something called R1 for the current prime number. The difference between two successive prime numbers is called Gap. As per Oppermann's Conjecture. the gap size would be on the order of
. This post is about estimating the Gap and not about the Conjecture per se.Read also the Table "80 known maximal prime gaps" https://en.wikipedia.org/wiki/Prime_gap. We will come back to Gap later in this post.
Let's start with the prime number 67
Our objective is to determine the next prime number without going through the division route.
Though we should use prime factors, I have used odd numbers as factors. This is a good starting point, though not as efficient.
Factors to be considered for 67 are 3,5,7,9,11 (We have taken 11 also though it could have been excluded.)
We now define R1.
R1 is another form of reminder when x is divided by y (both integers. All numbers are integers only unless otherwise specified).
R1 is the minimum number to be added to x to make the sum a multiple of y.
R1 values for 67 when divided by 3,5,7,9,11 are respectively: 2, 3, 3, 5, 10
Example:
67 +10=77 which is a multiple of 11
67+3=70 which is a multiple of both 5 and 7.
We now start from 67:
Find the first even number 2,4,6,8 etc which does NOT match any of the R1 (=2,3,3,5,10) AND SHOULD NOT MATCH ANY OF THE SUM OF FACTOR AND IT'S R1. The set of Sum of R1 and it's factor are {3+2, 5+3, 7+3, 9+5, 11+ 10}.
In this case it is 4. Add this 4 to the current prime.
In this case it is 4. Add this 4 to the current prime.
67+4=71.
71 hence is the next prime. BECAUSE THE SMALLEST EVEN NUMBER 4 IS NOT IN THE SET OF R1 NOR IN THE SET OF FACTOR + R1.
AND HENCE WHEN ADDED TO 67 WILL NOT BE EXACTLY DIVISIBLE BY ANY OF THE FACTORS.
AND HENCE WHEN ADDED TO 67 WILL NOT BE EXACTLY DIVISIBLE BY ANY OF THE FACTORS.
Now start with 71 and repeat.
For 71, R1 = 1,4,6,1,6. THE SET OF FACTORS + R1 IS {3+1,5+4,7+6,9+1,11+6}.
The smallest even number not in this set of R1 is 2.
The smallest even number not in this set of R1 is 2.
Hence the next prime is 71+2=73.
Now start with 73
R1=2,2,4,8,4. THE SET OF FACTORS + R1 IS {3+2,5+2,7+5,9+8,11+4}.
Smallest even number is 6.
Smallest even number is 6.
Start with 73+6=79
R1=2,1,5,2,9. THE SET OF FACTORS + R1 IS {3+2,5+1,7+5,9+2,11+9}.
Smallest even number not in R1 is 4.
Smallest even number not in R1 is 4.
79+4=83
FAQ
- Can this procedure be optimized further?
Yes. By considering fewer factors such as prime numbers only instead of odd numbers.
- When should we include a new factor or prime as a divisor?
When there is a new prime number whose square falls between N0 and N1, then we include that new prime as another factor. We find its R1, include it in our set and proceed as before.
More examples to show when the above simple formula fails:
Take a prime number 1301
Its Sq root is approx 36
Prime numbers less than 36:
3,5,7,11,13,17,19,23,29,31
R1 values of 1301 when divided by above prove numbers
3; 1
5: 4
7: 1
11: 8
13: 12
17: 8
19: 10
23: 10
29: 4
31: 1
Minimum even number in the set is 6. THE SET OF FACTOR + R1 IS {3+1,5+4,7+1,11+8,13+12,17+8,19+10,23+10,29+4}.
The next prime number after 1301 is 1301+6 = 1307.
An interesting example is prime number 113
The square root is approx 11.
The R1 values and R1 + factor values are
3; 1 3+1=4
5: 2 5+2=7
7: 6 7+6=13
11: 8 11+8=19
The minimum even number which is not in above sets {1,2,6,8}, {4,7,13,19} is 10. Adding 10 to 113 gives 123 which is divisible by 3. Hence our formula needs to be corrected. WE HAVE TO LOOK FOR THE LOWEST EVEN NUMBER WHICH IS NOT IN R1 NOR SHOULD IT BE IN THE SET OF (SUM OF R1 + n*factor) where n is any positive integer. That is, we have to look for the smallest even number from which when R1 is subtracted, the reminder is NOT a multiple of the factor; this should be true of each of the prime factors. Such an even number, that satisfies this condition, when added to N1 will give the next prime N2.
The even number 10 is R1+3*factor where factor is 3 and hence is eliminated. The next even number is 12 which is 2 (=R1 for 5) plus two times 5 and hence also eliminated.
Adding 12 would give a sum which is a multiple of 5.
The next even number is 14 which is the final answer. Hence the next prime number is 113+14.
When there is a small even number available in the set of R1 itself, then the other set of R1 +n*factor becomes irrelevant since these usually would be larger numbers and hence wouldn't affect the min obtained from R1.
Let's take the example of the prime which has a relatively high Gap. Let's find out this Gap
523 R1+n*factor (only evens upto 38)
R1
3: 2 8 14 20 26
5: 2 12 22 32
7: 2 16 30
11: 5 16 38
13: 10 36
17: 4 38
19: 9 28
23: 6
Prime factors up to 23 (=sq rt of 523) have been considered. Only such cases of n are taken that result in an even value for R1+n*factor . Odd values are irrelevant. Only sums up to approx 23 are needed. I have taken till 38. Even numbers 2,4,6,10 are in the 1st column showing R1. 8,12,14,16 are in the 2nd column. Hence the least even number not in either column is 18. This the Gap is 18 and hence the next prime is 531.
Now comes the interesting thing. The even number that when added to N1 gives N2 the next prime is the Gap. That even number, we know, is approximately the min value of R1. And hence that even number is less than the factors of N1. And the highest factor is the square root of N1. Thus, the Gap for N1 is less than the square root of N1 as mentioned in the top of the article. The Gap values, as seen in the wiki article mentioned at the top of this post, are indeed of the order of the square root of N1 or much less.
This is an interesting proof except for one thing. That the even number is NOT JUST the min value of R1.
We need to also consider the min of P = R1 + factor*n
That P could increase the Gap to potentially substantially more than the square root of N1. If we could prove that P is inconsequential then it is proved that Gap for N1 is less than sq rt (N1). Oppermann's Conjecture abstracts this further for (the square of) any number x, whether x is a prime number or not.
That between x^2 and x(x+1) there exists at least one prime number where x is any integer. The distance between the two algebraic expressions = x. Meaning that there exists a prime number at a distance of Sq Rt (x^2) from x^2 which is in sync with my own conclusion.
If the numbers N0, N1, N2 are three consecutive primes then I have suggested that N2 - N1 and N1 - N0 are both less than sq rt(N1). Take any composite number between N0 and N1. The primes N0 or N1 exists within a distance of sq rt (N1). There could be other primes even closer. The same is true of any composite number between N1 and N2. Oppermann's Conjecture could be rephrased as : For any integer X, there exists a prime number which is less than sqrt (x) distance away.
Another interesting fact is that I arrived at the conclusion that Gap generally does not exceed the square root of a prime number independently. My steps have been explained in this post.
In the attached Google spreadsheet here, in the "Merit and Maximal Gap" sheet we see empirically that the ratios of Gi/ln(Ni) and Ni/i (where Ni is the ith prime number, Gi is the the corresponding maximal Gap for Ni) are approximately equal. This is a strange result. Whether it apples to higher maximal Gaps is not known. This means that the maximal Gap G(i) is approximately about N(i)*ln(Ni)/i. Other Gaps will be even smaller.
If this result applies to higher primes as well, we have an ESTIMATE for the Gap since the current prime N(i), the value of i and the Gap are all known.
As I see for primes up to 5000, Gap that occurs most frequently is 6. Why 6? Why not 2 or any other even number? I think the reason is 6 is a multiple of 3. By adding a multiple of 3, we have already ensured that the new number is definitely not a factor of 3. Note 3 is also a multiple of 3 but 3 cannot be the Gap because 3 is odd.
Similarly one can say that Gap of 6*5 =30 is likely to be very frequent for high primes. Similarly 30*7=210, 210*11= 2310 etc are likely to be frequently occurring Gaps. The same thing is mentioned in https://golem.ph.utexas.edu/category/2016/03/the_most_common_prime_gaps.html
That leads to the question: Determine the first prime number that has a Gap of 210. Since 210 is a multiple of 3, 5, 7 the values across columns in the first the rows in Factor sheet is irrelevant. 210 will not be among the even numbers there. So, we need a scenario where (1) 210 does not exist but (2) all even numbers up to 208 do exist, at least in Union with the first three columns, in the first two columns across all rows.
Prime numbers less than 36:
3,5,7,11,13,17,19,23,29,31
R1 values of 1301 when divided by above prove numbers
3; 1
5: 4
7: 1
11: 8
13: 12
17: 8
19: 10
23: 10
29: 4
31: 1
Minimum even number in the set is 6. THE SET OF FACTOR + R1 IS {3+1,5+4,7+1,11+8,13+12,17+8,19+10,23+10,29+4}.
The next prime number after 1301 is 1301+6 = 1307.
An interesting example is prime number 113
The square root is approx 11.
The R1 values and R1 + factor values are
3; 1 3+1=4
5: 2 5+2=7
7: 6 7+6=13
11: 8 11+8=19
The minimum even number which is not in above sets {1,2,6,8}, {4,7,13,19} is 10. Adding 10 to 113 gives 123 which is divisible by 3. Hence our formula needs to be corrected. WE HAVE TO LOOK FOR THE LOWEST EVEN NUMBER WHICH IS NOT IN R1 NOR SHOULD IT BE IN THE SET OF (SUM OF R1 + n*factor) where n is any positive integer. That is, we have to look for the smallest even number from which when R1 is subtracted, the reminder is NOT a multiple of the factor; this should be true of each of the prime factors. Such an even number, that satisfies this condition, when added to N1 will give the next prime N2.
The even number 10 is R1+3*factor where factor is 3 and hence is eliminated. The next even number is 12 which is 2 (=R1 for 5) plus two times 5 and hence also eliminated.
Adding 12 would give a sum which is a multiple of 5.
The next even number is 14 which is the final answer. Hence the next prime number is 113+14.
When there is a small even number available in the set of R1 itself, then the other set of R1 +n*factor becomes irrelevant since these usually would be larger numbers and hence wouldn't affect the min obtained from R1.
Let's take the example of the prime which has a relatively high Gap. Let's find out this Gap
523 R1+n*factor (only evens upto 38)
R1
3: 2 8 14 20 26
5: 2 12 22 32
7: 2 16 30
11: 5 16 38
13: 10 36
17: 4 38
19: 9 28
23: 6
Prime factors up to 23 (=sq rt of 523) have been considered. Only such cases of n are taken that result in an even value for R1+n*factor . Odd values are irrelevant. Only sums up to approx 23 are needed. I have taken till 38. Even numbers 2,4,6,10 are in the 1st column showing R1. 8,12,14,16 are in the 2nd column. Hence the least even number not in either column is 18. This the Gap is 18 and hence the next prime is 531.
Now comes the interesting thing. The even number that when added to N1 gives N2 the next prime is the Gap. That even number, we know, is approximately the min value of R1. And hence that even number is less than the factors of N1. And the highest factor is the square root of N1. Thus, the Gap for N1 is less than the square root of N1 as mentioned in the top of the article. The Gap values, as seen in the wiki article mentioned at the top of this post, are indeed of the order of the square root of N1 or much less.
This is an interesting proof except for one thing. That the even number is NOT JUST the min value of R1.
We need to also consider the min of P = R1 + factor*n
That P could increase the Gap to potentially substantially more than the square root of N1. If we could prove that P is inconsequential then it is proved that Gap for N1 is less than sq rt (N1). Oppermann's Conjecture abstracts this further for (the square of) any number x, whether x is a prime number or not.
That between x^2 and x(x+1) there exists at least one prime number where x is any integer. The distance between the two algebraic expressions = x. Meaning that there exists a prime number at a distance of Sq Rt (x^2) from x^2 which is in sync with my own conclusion.
If the numbers N0, N1, N2 are three consecutive primes then I have suggested that N2 - N1 and N1 - N0 are both less than sq rt(N1). Take any composite number between N0 and N1. The primes N0 or N1 exists within a distance of sq rt (N1). There could be other primes even closer. The same is true of any composite number between N1 and N2. Oppermann's Conjecture could be rephrased as : For any integer X, there exists a prime number which is less than sqrt (x) distance away.
Another interesting fact is that I arrived at the conclusion that Gap generally does not exceed the square root of a prime number independently. My steps have been explained in this post.
In the attached Google spreadsheet here, in the "Merit and Maximal Gap" sheet we see empirically that the ratios of Gi/ln(Ni) and Ni/i (where Ni is the ith prime number, Gi is the the corresponding maximal Gap for Ni) are approximately equal. This is a strange result. Whether it apples to higher maximal Gaps is not known. This means that the maximal Gap G(i) is approximately about N(i)*ln(Ni)/i. Other Gaps will be even smaller.
If this result applies to higher primes as well, we have an ESTIMATE for the Gap since the current prime N(i), the value of i and the Gap are all known.
As I see for primes up to 5000, Gap that occurs most frequently is 6. Why 6? Why not 2 or any other even number? I think the reason is 6 is a multiple of 3. By adding a multiple of 3, we have already ensured that the new number is definitely not a factor of 3. Note 3 is also a multiple of 3 but 3 cannot be the Gap because 3 is odd.
Similarly one can say that Gap of 6*5 =30 is likely to be very frequent for high primes. Similarly 30*7=210, 210*11= 2310 etc are likely to be frequently occurring Gaps. The same thing is mentioned in https://golem.ph.utexas.edu/category/2016/03/the_most_common_prime_gaps.html
That leads to the question: Determine the first prime number that has a Gap of 210. Since 210 is a multiple of 3, 5, 7 the values across columns in the first the rows in Factor sheet is irrelevant. 210 will not be among the even numbers there. So, we need a scenario where (1) 210 does not exist but (2) all even numbers up to 208 do exist, at least in Union with the first three columns, in the first two columns across all rows.
Additional Reading
- https://www.researchgate.net/post/What_is_the_fastest_technique_to_find_the_next_prime_number_starting_from_a_given_prime_P
- https://www.quora.com/Is-there-a-pattern-to-the-prime-numbers "You wonder what the next prime will be. There is no way to find it without some testing."
- https://vbala99.blogspot.com/2016/05/estimating-fraction-of-numbers-that-are.html
- R1 values are provided in LOOKUP sheet in https://docs.google.com/spreadsheets/d/1nppxKrfkNOpI22NfzWP_ZNerC9wzvIBSJm8WOb9BqMQ/edit?usp=drivesdk. The first sheet calculates the next prime when given a prime.
- http://math.info/Arithmetic/Prime_Numbers_List/ List of prime numbers
- http://www.math.com/students/calculators/source/prime-number.htm - Is this number a prime?
No comments:
Post a Comment