New Maximal Gaps - Page 7

CraigLo · 2021-11-01, 05:46

This approach is only useful when it is needed to guarantee that a number is prime. For prime gap searches that probably means only maximal gap searches where we want to make sure we haven't missed any large gaps. The approach requires knowing all primes up to sqrt(N) so it couldn't be used for very large numbers. It might be useful up to 2⁸⁰.

Bobby Jacobs · 2022-03-01, 23:49

How far have you gotten in your search now? Have you found any new large prime gaps just above 2⁶⁴? Have you proven that 1552 and 1572 are maximal prime gaps?

rudy235 · 2022-03-02, 03:17

Quote:

Originally Posted by Bobby Jacobs

How far have you gotten in your search now? Have you found any new large prime gaps just above 2⁶⁴? Have you proven that 1552 and 1572 are maximal prime gaps?

I think that is a valid question. But I don’t think CraigLo would have forgotten to tell us.

Bobby Jacobs · 2022-05-07, 14:01

Well, Craig has not been on this site in a while. Does anybody else know how to prove the new maximal prime gaps?

rudy235 · 2022-07-19, 17:34

Quote:

Originally Posted by Bobby Jacobs

Well, Craig has not been on this site in a while. Does anybody else know how to prove the new maximal prime gaps?

it is “simple” each and every prime gap over a certain number (over 1400 or 1300 is a good bet) needs to be verified from 2⁶⁴ to 2⁶⁴ +2.33 X10¹⁶.
As far as I know ATH had checked up to 2⁶⁴ +1.05 X10¹⁶.
The first gaps that are still not known to be a first occurrence are

*1432
*1444
*1458
*1472
*1474
*1480
*1484
*1492
*1498
*1500
*1496

. If anyone know if any of this gaps has been proven to be a first occurrence, please let us know.

When the search is completed up to 18470057946260698231 ie 2⁶⁴ +2.33 X10¹⁶. then it will be (hopefully a new maximal gap.

Bobby Jacobs · 2022-08-13, 18:29

We should try to confirm these gaps ASAP. Where is the program to do it?

mart_r · 2023-02-20, 18:34

I don't know whether this idea has been considered before or whether it's practical, i.e. faster than previous searches:
Searching only for primes of the form 6k+1 (or 6k-1), and check for gaps > 1430. There should be one such gap every ~ 10^7 primes on average - or about 81 instances in a cycle of length 36*10^9. Then checking only these gaps for intermediate primes of the complementary form with a separate routine.
A Pari program I wrote was about 7% faster with this strategy compared to a classical search, but with Craig's approach there probably would be a lot more to gain. At the very best case it would be almost twice as fast.
Checking only e.g. 30k+1 would leave one gap every ~ 50th prime for a thorough check, which sounds like a great idea, but running a separate routine for every instance found - compared to a large sieve that covers the whole gamut - shows it's pretty much impractical. Maybe the best trade-off would be achieved somewhere between the forms 6k+1 and 30k+{1,17}?

rudy235 · 2023-02-20, 23:51

To my understanding , (except for 2 and 3) all primes are of the form 6K+1 or 6k -1 so there must be something I did not quite get in the previous post.

Nevertheless the “things” that remain unsolved are
a) Is 1370 the 81st Maximal gap
b) is 1572 the 82nd Maximal gap
c) Have any newer Smaller occurrences of first time gaps been found?
I.e of these gaps?
*1432
*1444
*1458
*1472
*1474
*1480
*1484
*1492
*1496
*1498
*1500
d) What is the current limit of exhaustive search over 2⁶⁴+10^{^16}?

Andrew Usher · 2023-02-21, 11:59

He means sieving only one of the types mod 6 to find all possibilities for large enough gaps, then checking on the other side only within those - or something with that effect. It does look possibly attractive to do so.

I agree that it seems silly that those two maximal gaps haven't been confirmed and I'm not sure exactly what the reason is, but they should be at the top of the list for 'things to do related to prime gaps'.

mart_r · 2023-02-21, 16:50

@ rudy235: It's like Andrew said, looking only at one residue mod 6, since 1432 is a large gap that requires a merit of > 16 when looking only at those numbers. This should be rare enough that there shuold be a benefit in searching only this type, and only check those intervals for the other type (the other residue mod 6) when a large enough gap is found.
Realistically, I would expect a speedup of maybe 10 to 30%, but I'm not familiar enough with how Craig is checking the gaps after all primes are computed.

Craig's code for 65-bit numbers, which involves customized GPU usage, is fast - about 1.5*10¹¹/sec, there's a lot of stuff going on in parallel, but does only one Fermat test after sufficient sieving, which is not enough to call the search "exhaustive" (although the probability that one first occurrence gap has been overlooked is near zero, well, the < 10^-9 type of zero :). Doing all necessary prime tests would make the code about 10x slower.
There's a lot of background info in this thread, but the search itself is on hiatus since 2021.

Regarding c), beside the two new maximal gaps, Craig has only found one 1510 and one 1446, all others are smaller than 1432.
Regarding d), ATH has searched up to 2⁶⁴+1.05*10¹⁶, but even this search wasn't necessarily exhaustive, see post # 15 in the above mentioned thread. So strictly speaking we're still standing at the 64-bit border with the exhaustive search.

Bobby Jacobs · 2023-02-23, 17:38

Quote:

Originally Posted by rudy235

Nevertheless the “things” that remain unsolved are
a) Is 1370 the 81st Maximal gap
b) is 1572 the 82nd Maximal gap

1370 is the 73rd maximal prime gap. We really want to know if 1552 is the 81st maximal prime gap.

2023-02-21, 16:50	#76
mart_r Dec 2008 you know...around... 887 Posts	@ rudy235: It's like Andrew said, looking only at one residue mod 6, since 1432 is a large gap that requires a merit of > 16 when looking only at those numbers. This should be rare enough that there shuold be a benefit in searching only this type, and only check those intervals for the other type (the other residue mod 6) when a large enough gap is found. Realistically, I would expect a speedup of maybe 10 to 30%, but I'm not familiar enough with how Craig is checking the gaps after all primes are computed. Craig's code for 65-bit numbers, which involves customized GPU usage, is fast - about 1.510¹¹/sec, there's a lot of stuff going on in parallel, but does only one Fermat test after sufficient sieving, which is not enough to call the search "exhaustive" (although the probability that one first occurrence gap has been overlooked is near zero, well, the < 10^-9 type of zero :). Doing all necessary prime tests would make the code about 10x slower. There's a lot of background info in this thread, but the search itself is on hiatus since 2021. Regarding c), beside the two new maximal gaps, Craig has only found one 1510 and one 1446, all others are smaller than 1432. Regarding d), ATH has searched up to 2⁶⁴+1.0510¹⁶, but even this search wasn't necessarily exhaustive, see post # 15 in the above mentioned thread. So strictly speaking we're still standing at the 64-bit border with the exhaustive search. Last fiddled with by mart_r on 2023-02-21 at 16:54 Reason: typo

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Guess the next maximal prime gap.	Bobby Jacobs	Prime Gap Searches	7	2022-08-28 12:12
Gaps between maximal prime gaps	Bobby Jacobs	Prime Gap Searches	52	2020-08-22 15:20
Superprime gaps	Bobby Jacobs	Prime Gap Searches	5	2019-03-17 20:01
Top 50 gaps	robert44444uk	Prime Gap Searches	1	2018-07-10 20:50
Gaps and more gaps on <300 site	gd_barnes	Riesel Prime Search	11	2007-06-27 04:12

2021-11-01, 05:46	#67
CraigLo Mar 2021 73₈ Posts	This approach is only useful when it is needed to guarantee that a number is prime. For prime gap searches that probably means only maximal gap searches where we want to make sure we haven't missed any large gaps. The approach requires knowing all primes up to sqrt(N) so it couldn't be used for very large numbers. It might be useful up to 2⁸⁰.

2022-03-01, 23:49	#68
Bobby Jacobs May 2018 2·3·7² Posts	How far have you gotten in your search now? Have you found any new large prime gaps just above 2⁶⁴? Have you proven that 1552 and 1572 are maximal prime gaps?

2022-05-07, 14:01	#70
Bobby Jacobs May 2018 2·3·7² Posts	Well, Craig has not been on this site in a while. Does anybody else know how to prove the new maximal prime gaps?

2022-08-13, 18:29	#72
Bobby Jacobs May 2018 2·3·7² Posts	We should try to confirm these gaps ASAP. Where is the program to do it?

2023-02-20, 18:34	#73
mart_r Dec 2008 you know...around... 887 Posts	I don't know whether this idea has been considered before or whether it's practical, i.e. faster than previous searches: Searching only for primes of the form 6k+1 (or 6k-1), and check for gaps > 1430. There should be one such gap every ~ 10^7 primes on average - or about 81 instances in a cycle of length 36*10^9. Then checking only these gaps for intermediate primes of the complementary form with a separate routine. A Pari program I wrote was about 7% faster with this strategy compared to a classical search, but with Craig's approach there probably would be a lot more to gain. At the very best case it would be almost twice as fast. Checking only e.g. 30k+1 would leave one gap every ~ 50th prime for a thorough check, which sounds like a great idea, but running a separate routine for every instance found - compared to a large sieve that covers the whole gamut - shows it's pretty much impractical. Maybe the best trade-off would be achieved somewhere between the forms 6k+1 and 30k+{1,17}?

2023-02-20, 23:51	#74
rudy235 Jun 2015 Vallejo, CA/. 1162₁₀ Posts	To my understanding , (except for 2 and 3) all primes are of the form 6K+1 or 6k -1 so there must be something I did not quite get in the previous post. Nevertheless the “things” that remain unsolved are a) Is 1370 the 81st Maximal gap b) is 1572 the 82nd Maximal gap c) Have any newer Smaller occurrences of first time gaps been found? I.e of these gaps? 1432 1444 1458 1472 1474 1480 1484 1492 1496 1498 *1500 d) What is the current limit of exhaustive search over 2⁶⁴+10^{^16}?

2023-02-21, 11:59	#75
Andrew Usher Dec 2022 2⁶×7 Posts	He means sieving only one of the types mod 6 to find all possibilities for large enough gaps, then checking on the other side only within those - or something with that effect. It does look possibly attractive to do so. I agree that it seems silly that those two maximal gaps haven't been confirmed and I'm not sure exactly what the reason is, but they should be at the top of the list for 'things to do related to prime gaps'.