New Maximal Gaps
 

I found this yesterday
1552 34.9844 18470057946260698231


It isn't proven maximal. I was only sieving and doing a single Fermat test. Does anyone want to help prove this is a new maximal gap? I think ATH has already checked up to at least 2^64 + 7734466511986395.

[URL]https://www.mersenneforum.org/showpost.php?p=521550&postcount=69[/URL]

Nice!

I'm happy to throw some CPU at it if someone else coordinates.
I would also require instructions

Congratulation!

How did you find it, did you start at some random location or used some criteria? Which software did you use?

I reached 2[SUP]64[/SUP] + 1.05*10[SUP]16[/SUP] = 18,457,244,073,709,551,616 but I have not worked on it recently. The gap is at 2[SUP]64[/SUP] + 2.33*10[SUP]16[/SUP] so I'm not even half way.

Congratulations! I was expecting the next maximal prime gap after 1550 to be at least 1600. I am surprised that this gap is only 2 greater than the last maximal gap. However, it is great that you found this gap.

Astounding, many congrats.

Lets hope it is a new maximal!

[QUOTE=CraigLo;581405]I found this yesterday
1552 34.9844 18470057946260698231


It isn't proven maximal. I was only sieving and doing a single Fermat test. Does anyone want to help prove this is a new maximal gap? I think ATH has already checked up to at least 2^64 + 7734466511986395.

[URL]https://www.mersenneforum.org/showpost.php?p=521550&postcount=69[/URL][/QUOTE]

Congrats, nice find! Let's hope it's a max gap.

Ps forgive my curiosity Craig, but how much calculating power (threads, cores) do you have at your disposal? The number of improvements you submit each time, gives me the idea it must be substantial.

Kind regards
Michiel Jansen

[QUOTE=ATH;581410]Congratulation!

How did you find it, did you start at some random location or used some criteria? Which software did you use?

I reached 2[SUP]64[/SUP] + 1.05*10[SUP]16[/SUP] = 18,457,244,073,709,551,616 but I have not worked on it recently. The gap is at 2[SUP]64[/SUP] + 2.33*10[SUP]16[/SUP] so I'm not even half way.[/QUOTE]

Thanks. I started at 2^64. I've been writing GPU code. It is still under development and needs more testing. I'll post my code on github when it is finished if anyone is interested.

Did you save any gaps other than the maximal gaps above 2^64 that you posted? I saved all gaps above 1000 up to about 2^64 + 2E16. Anything you could send me would be helpful in testing.

[QUOTE=MJansen;581437]Congrats, nice find! Let's hope it's a max gap.

Ps forgive my curiosity Craig, but how much calculating power (threads, cores) do you have at your disposal? The number of improvements you submit each time, gives me the idea it must be substantial.

Kind regards
Michiel Jansen[/QUOTE]

Thanks. I use 1 1080 TI. My code doesn't work well for large numbers so I decided to switch to the max gap search until I have time to rewrite it. I planned to run it over the summer with the hope of finding 1 new record above 1432. I got lucky that this gap is so close to the previous max gap.

[QUOTE=CraigLo;581442]Thanks. I started at 2^64. I've been writing GPU code. It is still under development and needs more testing. I'll post my code on github when it is finished if anyone is interested.

Did you save any gaps other than the maximal gaps above 2^64 that you posted? I saved all gaps above 1000 up to about 2^64 + 2E16. Anything you could send me would be helpful in testing.[/QUOTE]

I mostly saved that "maximal gap" list I made for fun starting at 0 at 2[SUP]64[/SUP], which you already linked.
I did save some gaps > 1000 but only briefly in the beginning. My program jumps ahead the minimum gapsize I want to find and then searches backwards until it finds a prime, if I set minimum gapsize to 1000 it would run even slower than it already does when I have it at 1320 which is my "maximal gap" above 2[SUP]64[/SUP].
I do not think this is an exhaustive list of gaps > 1000 even in the internal it covers, because I might have turned on and off the feature of saving gaps>1000, I do not remember exactly, but I guess you can test if your program has found these gaps. Very exciting with GPU code for this, I did dream about making my program for GPU, but I never found the motivation to learn programming for GPUs.

[CODE]GAP: 1062 M=23.9397 CSG=0.539652 18446747749629047369 = 2^64+3675919495753
GAP: 1050 M=23.6692 CSG=0.533554 18446749424543324977 = 2^64+5350833773361
GAP: 1010 M=22.7675 CSG=0.513228 18446749672316868389 = 2^64+5598607316773
GAP: 1036 M=23.3536 CSG=0.52644 18446757511464660451 = 2^64+13437755108835
GAP: 1044 M=23.534 CSG=0.530505 18446760966709446359 = 2^64+16892999894743
GAP: 1008 M=22.7224 CSG=0.512212 18446762802362416693 = 2^64+18728652865077
GAP: 1024 M=23.0831 CSG=0.520342 18446763681622535443 = 2^64+19607912983827
GAP: 1014 M=22.8577 CSG=0.515261 18446764906595085317 = 2^64+20832885533701
GAP: 1034 M=23.3085 CSG=0.525424 18446769723502347797 = 2^64+25649792796181
GAP: 1152 M=25.9685 CSG=0.585385 18446779902697426681 = 2^64+35828987875065
GAP: 1002 M=22.5872 CSG=0.509163 18446787953189723131 = 2^64+43879480171515
GAP: 1046 M=23.579 CSG=0.531521 18446795884964577593 = 2^64+51811255025977
GAP: 1028 M=23.1733 CSG=0.522375 18446809183097018309 = 2^64+65109387466693
GAP: 1014 M=22.8577 CSG=0.515261 18446814868797283063 = 2^64+70795087731447
GAP: 1066 M=24.0299 CSG=0.541684 18446815504958901043 = 2^64+71431249349427
GAP: 1082 M=24.3906 CSG=0.549815 18446826240052088519 = 2^64+82166342536903
GAP: 1008 M=22.7224 CSG=0.512212 18446832337462467179 = 2^64+88263752915563
GAP: 1010 M=22.7675 CSG=0.513228 18446834480319631049 = 2^64+90406610079433
GAP: 1032 M=23.2635 CSG=0.524407 18446837965455400181 = 2^64+93891745848565
GAP: 1026 M=23.1282 CSG=0.521358 18446839378382506093 = 2^64+95304672954477
GAP: 1050 M=23.6692 CSG=0.533554 18446839576483513649 = 2^64+95502773962033
GAP: 1028 M=23.1733 CSG=0.522375 18446839708582188941 = 2^64+95634872637325
GAP: 1020 M=22.9929 CSG=0.51831 18446842024842919381 = 2^64+97951133367765
GAP: 1044 M=23.534 CSG=0.530505 18446852276777385049 = 2^64+108203067833433
GAP: 1012 M=22.8126 CSG=0.514244 18446855924744238139 = 2^64+111851034686523
GAP: 1020 M=22.9929 CSG=0.51831 18446858566936374767 = 2^64+114493226823151
GAP: 1004 M=22.6323 CSG=0.510179 18446859568323746303 = 2^64+115494614194687
GAP: 1092 M=24.616 CSG=0.554896 18446866320952044589 = 2^64+122247242492973
GAP: 1008 M=22.7224 CSG=0.512212 18446869081479001931 = 2^64+125007769450315
GAP: 1002 M=22.5872 CSG=0.509163 18446870028613768249 = 2^64+125954904216633
GAP: 1026 M=23.1282 CSG=0.521358 18446877536936961383 = 2^64+133463227409767
GAP: 1044 M=23.534 CSG=0.530505 18446878448228545247 = 2^64+134374518993631
GAP: 1050 M=23.6692 CSG=0.533554 18446881999487799761 = 2^64+137925778248145
GAP: 1060 M=23.8946 CSG=0.538635 18446882369862589303 = 2^64+138296153037687
GAP: 1040 M=23.4438 CSG=0.528472 18446884791762922619 = 2^64+140718053371003
GAP: 1026 M=23.1282 CSG=0.521358 18446885204269142597 = 2^64+141130559590981
GAP: 1036 M=23.3536 CSG=0.52644 18446885242027025197 = 2^64+141168317473581
GAP: 1016 M=22.9028 CSG=0.516277 18446890318078148273 = 2^64+146244368596657
GAP: 1008 M=22.7224 CSG=0.512212 18446894754557835029 = 2^64+150680848283413
GAP: 1016 M=22.9028 CSG=0.516277 18447124224395493323 = 2^64+380150685941707
GAP: 1038 M=23.3987 CSG=0.527456 18447124475560111561 = 2^64+380401850559945
GAP: 1038 M=23.3987 CSG=0.527456 18447144890682053239 = 2^64+400816972501623
GAP: 1038 M=23.3987 CSG=0.527456 18447164069237234579 = 2^64+419995527682963
GAP: 1068 M=24.075 CSG=0.5427 18447166052641000471 = 2^64+421978931448855
GAP: 1192 M=26.8702 CSG=0.60571 18447174410466704389 = 2^64+430336757152773
GAP: 1054 M=23.7594 CSG=0.535586 18447194450543281309 = 2^64+450376833729693[/CODE]

[QUOTE=CraigLo;581405]I found this yesterday
1552 34.9844 18470057946260698231


It isn't proven maximal. I was only sieving and doing a single Fermat test. Does anyone want to help prove this is a new maximal gap? I think ATH has already checked up to at least 2^64 + 7734466511986395.

[URL]https://www.mersenneforum.org/showpost.php?p=521550&postcount=69[/URL][/QUOTE]


Congrats! That's a spectacular result, albeit a rather lucky one.:smile:
At the current rate of progress, I wouldn't have expected the next maximal gap to be found so soon.

Even if does not become the new maximal gap. (I would say it has a better than even chance of being that) it will almost certainly become the first occurrence of a gap of 1552. So you won’t go empty handed!

CONGRATULATIONS!

[QUOTE=CraigLo;581405]I found this yesterday
1552 34.9844 18470057946260698231

It isn't proven maximal. I was only sieving and doing a single Fermat test. [/QUOTE]

That is great! So we were really close to this (p ~ 2^64+23e15) by our exhaustive search up to 2^64 with my code (+some code improvements from users here).

GPU Prime Gap searching
 

[QUOTE=mart_r;581449]Congrats! That's a spectacular result, albeit a rather lucky one.:smile:
At the current rate of progress, I wouldn't have expected the next maximal gap to be found so soon.[/QUOTE]

It was definitely lucky. 2^64 + 2.3E16 is only 0.59% higher than the previous max gap. The average step is around 70% which would have taken 3 years instead of a few days. Although there are 3 max gaps closer to the previous max gap so it isn't totally unexpected.
Gap = 132, 0.56%
Gap = 514, 0.40%
Gap = 1132, 0.37%

[QUOTE=ATH;581446]I mostly saved that "maximal gap" list I made for fun starting at 0 at 2[SUP]64[/SUP], which you already linked.
I did save some gaps > 1000 but only briefly in the beginning. My program jumps ahead the minimum gapsize I want to find and then searches backwards until it finds a prime, if I set minimum gapsize to 1000 it would run even slower than it already does when I have it at 1320 which is my "maximal gap" above 2[SUP]64[/SUP].
I do not think this is an exhaustive list of gaps > 1000 even in the internal it covers, because I might have turned on and off the feature of saving gaps>1000, I do not remember exactly, but I guess you can test if your program has found these gaps. Very exciting with GPU code for this, I did dream about making my program for GPU, but I never found the motivation to learn programming for GPUs.
[/QUOTE]

My code found all of these so it seems to be working pretty well. Thanks.

[QUOTE=R. Gerbicz;581500]That is great! So we were really close to this (p ~ 2^64+23e15) by our exhaustive search up to 2^64 with my code (+some code improvements from users here).[/QUOTE]

What does your code use for testing primes?

@CraigLo there is no need to quote an entire post when responding.

Have you found any other first occurrence gaps besides this one?

It used to be that new first occurrences and/or new maximal gaps were reported to Dr. Nicely. Unfortunately as we all know he passed away on October 2019.

This is the first time I am aware a new first occurrence has happened [B]in the table from 1 to 1998[/B]
The entry. 1552 C?C Spielaur 2017 28.15 24 876129783640337274493519
Should be replaced by a similar one with the information of CraigLo
[B]1552 C?C CraigLo 2021 34.98 20 18470057946260698231[/B]

This is independently of the gap being found to be maximal or not.

How has, for instance, our friend robert4444uk been reporting his many first occurrences in other sections of the Tables?

Hi Rudy235,

Seth Troisi keeps a github database that has all the record gaps. A view can be found at : [url]https://primegap-list-project.github.io/lists/prime-gaps-high-watermarks/[/url] this page included Craig's newfound 1552 gap. More lists can be found at: [url]https://primegap-list-project.github.io/lists/[/url].

The entry page is off line now, but can be found at: [url]https://primegaps.cloudygo.com/[/url]

Kind regards
Michiel

The second largest gap I've found so far is 1430.

[QUOTE=MJansen;582083]Hi Rudy235,



The entry page is off line now, but can be found at: [url]https://primegaps.cloudygo.com/[/url]

Kind regards
Michiel[/QUOTE]

Hi - does anyone know when the entry page is coming back online?

Seth just send a PM, he is moving house in the middle of the heat-wave. Takes a little longer to set up internet again. So a little patience, he'll be back ;-)

I have internet setup now and I'm busy running ethernet cables all over. Thanks for everyone's patience and DMs checking if I was okay. The server should hopefully be up by Sunday morning.

[QUOTE=SethTro;582464]I have internet setup now and I'm busy running ethernet cables all over. Thanks for everyone's patience and DMs checking if I was okay. The server should hopefully be up by Sunday morning.[/QUOTE]

The input page is now working [URL="https://primegaps.cloudygo.com/"]https://primegaps.cloudygo.com/[/URL]

Why I am underwhelmed by the last few maximal prime gaps
 

The last few maximal prime gaps seemed smaller than the expected maximal prime gap. Now, I know why. In another post, I conjectured that the maximum prime gap between primes up to p is approximately ln[SUP]2[/SUP](p)-(2*ln(p)*ln(ln(p))). I defined the Jacobs value of a gap to be (g-ln[SUP]2[/SUP](p)+(2*ln(p)*ln(ln(p))))/ln(p). Then, a Jacobs value of 0 would be an average maximal gap, a value of 1 would be a big maximal gap, and a value of -1 would be a small maximal gap. Here are the Jacobs values of the known maximal gaps.

2, 3, 1, -2.774068078741657E-4
3, 5, 2, 0.5850019473393445
7, 11, 4, 1.0194170587459925
23, 29, 6, 0.8427693920801025
89, 97, 8, 0.2151204218932354
113, 127, 14, 1.2014335975957555
523, 541, 18, 0.24572021013679826
887, 907, 20, -0.03652024352158025
1129, 1151, 22, -0.02150721463226403
1327, 1361, 34, 1.448387619815254
9551, 9587, 36, -0.8100577183892048
15683, 15727, 44, -0.5731101097730286
19609, 19661, 52, -0.044318784730949315
31397, 31469, 72, 1.270502655772665
155921, 156007, 86, 0.19713225629640171
360653, 360749, 96, -0.19530119032678306
370261, 370373, 112, 1.0149060902113427
492113, 492227, 114, 0.7373958069907232
1349533, 1349651, 118, -0.4611403308640233
1357201, 1357333, 132, 0.5220568928672134
2010733, 2010881, 148, 1.033147878685969
4652353, 4652507, 154, 0.14036146068116476
17051707, 17051887, 180, -0.21707747686074932
20831323, 20831533, 210, 1.258402597454145
47326693, 47326913, 220, 0.5200965832122922
122164747, 122164969, 222, -0.8502170210370023
189695659, 189695893, 234, -0.8892319752420521
191912783, 191913031, 248, -0.1730735352653388
387096133, 387096383, 250, -1.1626831960005015
436273009, 436273291, 282, 0.2623201147347242
1294268491, 1294268779, 288, -1.1673904115852733
1453168141, 1453168433, 292, -1.1579267965057205
2300942549, 2300942869, 320, -0.5705701565499374
3842610773, 3842611109, 336, -0.6563443731836452
4302407359, 4302407713, 354, -0.025270036477032205
10726904659, 10726905041, 382, -0.27705464505393207
20678048297, 20678048681, 384, -1.250147345715678
22367084959, 22367085353, 394, -0.9557070199950923
25056082087, 25056082543, 456, 1.4512178681058923
42652618343, 42652618807, 464, 0.8761319444431268
127976334671, 127976335139, 468, -0.7928312132556395
182226896239, 182226896713, 474, -1.1368024109318071
241160624143, 241160624629, 486, -1.133103779054893
297501075799, 297501076289, 490, -1.3230610013550814
303371455241, 303371455741, 500, -0.9765903793850329
304599508537, 304599509051, 514, -0.45375859265074997
416608695821, 416608696337, 516, -0.8961227372483432
461690510011, 461690510543, 532, -0.4692611765107444
614487453523, 614487454057, 534, -0.8689218000292784
738832927927, 738832928467, 540, -0.9527802901109655
1346294310749, 1346294311331, 582, -0.43007067428120926
1408695493609, 1408695494197, 588, -0.2914020442057517
1968188556461, 1968188557063, 602, -0.3558643155112367
2614941710599, 2614941711251, 652, 0.9173811138146628
7177162611713, 7177162612387, 674, -0.0574570952912501
13829048559701, 13829048560417, 716, 0.22504080783702007
19581334192423, 19581334193189, 766, 1.264869125563402
42842283925351, 42842283926129, 778, 0.2904504058143198
90874329411493, 90874329412297, 804, -0.18509610871942694
171231342420521, 171231342421327, 806, -1.202125940325487
218209405436543, 218209405437449, 906, 1.4183818893463445
1189459969825483, 1189459969826399, 916, -1.2297298698358887
1686994940955803, 1686994940956727, 924, -1.5939815003889521
1693182318746371, 1693182318747503, 1132, 4.331590450308519
43841547845541059, 43841547845542243, 1184, -0.1292269969948478
55350776431903243, 55350776431904441, 1198, -0.17389157190416654
80873624627234849, 80873624627236069, 1220, -0.27108837564182264
203986478517455989, 203986478517457213, 1224, -1.7763241380075703
218034721194214273, 218034721194215521, 1248, -1.2896653554305229
305405826521087869, 305405826521089141, 1272, -1.2753733168794827
352521223451364323, 352521223451365651, 1328, -0.13791061617203643
401429925999153707, 401429925999155063, 1356, 0.32401793693094755
418032645936712127, 418032645936713497, 1370, 0.5971215852470018
804212830686677669, 804212830686679111, 1442, 1.1853125062362995
1425172824437699411, 1425172824437700887, 1476, 0.9753154533071884
5733241593241196731, 5733241593241198219, 1488, -1.2112885884477058
6787988999657777797, 6787988999657779307, 1510, -0.9991650401801192
15570628755536096243, 15570628755536097769, 1526, -2.0836332971905804
17678654157568189057, 17678654157568190587, 1530, -2.213542051864597
18361375334787046697, 18361375334787048247, 1550, -1.8283253937088773

Notice that most of the maximal gaps have a Jacobs value between -2 and 2. A weird anomaly is the gap of 1132, which has a Jacobs value of 4.33. The gaps of 1526 and 1530 are the only maximal gaps with a Jacobs value below -2. The gap of 1550 is almost at -2. If this gap of 1552 is a maximal gap, then it will also have a low Jacobs value. That is why I believe we should have a lot bigger maximal prime gaps.

I got really lucky and found another.


1572 35.4308 18571673432051830099

Amazing work Craig!


It's great to see the lower bound pushed upwards!

Gratz again!

Did you really test everything up to 2[SUP]64[/SUP] + 1.249 * 10[SUP]17[/SUP] ?
This is 5.36 times further from 2[SUP]64[/SUP] than your last gap.

What speed are you getting on the 1080 TI ? Either in time per interval, like time per 10[SUP]12[/SUP] or whatever, or interval per time, how far per hour or per day?

This is so exciting. We now have a "probable maximum gap" with the highest merit of all gaps that have a good chance of being maximal. There are gaps with much higher merits but almost no chance of becoming maximal.

1572 [B][COLOR="Red"]35.4308[/COLOR][/B] 18571673432051830099

Previous Maximal Gaps in order of Merit.[LIST=1]1476 P19 = 1425172824437699411 [B]35.3103[/B][*]1552 PRP20 = 18470057946260698231 34.9844[*]1442 P18 = 804212830686677669 [B]34.9757[/B][*]1550 P20 = 18361375334787046697 34.9439[*]1510 P19 = 6787988999657777797 34.8234[*]1530 P20 = 17678654157568189057 34.5225[*]1526 P20 = 15570628755536096243 34.5312[/LIST]So, should it become a maximal gap it will have the highest merit of all the maximals.

Congratulations.

Edit: The second gap in the list -1552- gap is not yet proven to be maximal.:smile:

Looking for gaps >= 1300 I search about 150E9/sec = 1.3E16/day. That's sieving with about 10k primes and doing 1 Fermat test.

Congratulations on finding another gap! It is amazing that there are so many maximal prime gaps so logarithmically close to the binary round number 2[SUP]64[/SUP].

[QUOTE=CraigLo;583218]I got really lucky and found another.


1572 35.4308 18571673432051830099[/QUOTE]

Astonishing!

[QUOTE=CraigLo;583218]I got really lucky and found another.


1572 35.4308 18571673432051830099[/QUOTE]

i looked for it at the prime gap tables and it was not there. Did you report it?

[QUOTE=rudy235;584122]i looked for it at the prime gap tables and it was not there. Did you report it?[/QUOTE]

That's on me, the primegap github site is updated manually ~monthly. I updated it today. 1572 now appears on [URL]https://primegap-list-project.github.io/lists/prime-gaps-high-watermarks/[/URL]

Have the new gaps of 1552 and 1572 been confirmed as maximal prime gaps yet? How close are you to confirming them?

I don't think anyone is working on confirming them. My code can't be used for confirmation. I don't have much CPU resources to contribute and I'm not sure what code others have used. I might be able to help speed up some of the existing CPU code.

I've checked up to 2[SUP]64[/SUP] + 61*10[SUP]16[/SUP]. In addition to the 1552 and 1572 I found 7 gaps in the 1400s but the largest is still 1430 so no new first occurrences.

I thought you started at 2[SUP]64[/SUP] and worked continuously from there. How are you not sure that these are maximal prime gaps? Did you skip any primes?

[QUOTE]
I reached 264 + 1.05*1016 = 18,457,244,073,709,551,616 but I have not worked on it recently. The gap is at 264 + 2.33*1016 so I'm not even half way.[/QUOTE] ATH


This is the status of the exhaustive search. (Unless someone else has covered the numbers after 2[SUP]64[/SUP]+1.03 x10[SUP]16[/SUP])

To check in a reliable way that no gap greater or equal to [SIZE="5"][b]1432 [/b][/SIZE] exists below 2[SUP]64[/SUP] +2.33x10[SUP]16[/SUP]where the gap of 1552 is found is a gruesome task as we no longer have the support of the code that allowed us to reach 2[SUP]64[/SUP]-2[SUP]32[/SUP].

As things stand now the smallest gap that we don’t know with certainty to be a “first occurrence” is 1432.

I checked continuously from 2[SUP]64[/SUP] but I'm only doing 1 Fermat test so it is possible that a number is incorrectly called a prime. I think it is unlikely that this has lead to missing a large gap (very unlikely if the math in this post is correct [url]https://mersenneforum.org/showpost.php?p=583288&postcount=20[/url]) but it is still possible. The easiest way for me to fix this issue would be to use 12 SPRP tests which is sufficient to prove primality. Half the remaining numbers are prime after sieving so the code would take about 6-7 times longer to run. It's possible it would be faster to check with sieving only. It would require sieving up to primes a little above 2[SUP]32[/SUP].

This is also new GPU code so it is possible that there is some other error. I did find all the gaps above 1000 that ATH found so there is some confidence that it is working correctly.

[QUOTE=CraigLo;586408]The easiest way for me to fix this issue would be to use 12 SPRP tests which is sufficient to prove primality. Half the remaining numbers are prime after sieving so the code would take about 6-7 times longer to run. [/QUOTE]

It would be faster with 1 SPRP + 1 Lucas than 12 SPRP. At least the CPU code with the GMP library 1 Lucas test is about equal to 6.4-6.6 SPRP tests at 2[SUP]64[/SUP] + 2*10[SUP]16[/SUP].
Why does 12 SPRP tests prove primality?

[QUOTE=ATH;586415]
Why does 12 SPRP tests prove primality?[/QUOTE]

I was wondering exactly the same thing. On the other hand, a number of the order of 10^19 can be proven prime easily by trial division or sieving.

Keeking track of the Numbers that STILL have not yet been established as a First Occurrence Gap. (The last one 1552 [U]is most probably[/U] a first occurrence and thus a Maximal Gap)[list][*]1432[*]1444[*]1458[*]1472[*]1474[*]1478[*]1480[*]1484[*]1492[*]1496[*]1498[*]1500[*]1504[*]1508[*]1512[*]1514[*]1516[*]1518[*]1520[*]1522[*]1524[*]1528[*]1532[*]1534[*]1536[*]1538[*]1540[*]1542[*]1544[*]1546[*]1548[*]1552[/LIST]
I am assuming none of these numbers, with the exception of 1552, have been improved since November 2019

Bases of 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 have been proven a deterministic test up to 3.18 * 10[SUP]23[/SUP].
[url]https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test[/url]

For 2[SUP]65[/SUP] this can likely be reduced to 7 or better but I don't think it has been proven beyond 2[SUP]64[/SUP].
[url]https://miller-rabin.appspot.com/[/url]

There is a list of base 2 pseudoprimes up to 2[SUP]64[/SUP].
[url]http://www.janfeitsma.nl/math/psp2/index[/url]

When you guys were doing the search up to 2[SUP]64[/SUP] it would have been faster to do the Lucas test only if the number was a known 2-PSP.

Unfortunately the list only goes up to 2[SUP]64[/SUP]. Is there a fast way to generate the list of 2-PSP. When checking for gaps we need to do one Lucas test for every 1400 numbers. To check from 2[SUP]64[/SUP] to 2[SUP]64[/SUP] + 2.33 * 10[SUP]16[/SUP] (Gap=1552) would require 1.66*10[SUP]13[/SUP] Lucas tests. Can the list of 2-PSP be computed faster than this? We wouldn't even need to rerun what has already been done. We could just check for large gaps around the 2-PSPs.

Edit to above:
There was no need to do the Lucas test at all. If it is a 2-PSP it is known to be composite. You could check if it is a 2-PSP before doing the PRP test. I would probably do this by adding the list of 2-PSPs into the sieve.

Also, it might be inefficient to do a SPRP test and Lucas test in the GPU. The parallel threads in a block need to execute the same instruction so some threads would probably sit idle while others were doing a Lucas test.

This might work ...
If n is a 2-psp (pseudoprime to base 2) and prime p divides n then
[CODE]n = p, mod (p*ord(p))[/CODE]
where ord(p) is the multiplicative order of 2 mod p
([url]https://www.ams.org/journals/mcom/1980-35-151/S0025-5718-1980-0572872-7/S0025-5718-1980-0572872-7.pdf[/url])

This can be used to sieve for numbers that are possible 2-psp. ord(p) is usually about as large as p so the product is ~p[SUP]2[/SUP]. This makes the psp-sieve much faster than a regular sieve.

The algorithm:
1. Find all primes up to sqrt(N) = 2[SUP]32.5[/SUP] if we want to check up to 2[SUP]65[/SUP].
2. Precompute ord(p) for all primes.

3. Use regular sieve with small primes. I currently use ~10k primes which is probably a good starting point. This greatly reduces the number of potential primes that need to be checked with a fermat test.

4. Use the psp-sieve with all remaining primes. This guarantees that a number is prime if it passes the fermat test and isn't removed by either sieve. This should be fast because p*ord(p) >> p. In many cases p*ord(p) will be so large that it will only occur a few times in the interval 2[SUP]64[/SUP] to 2[SUP]65[/SUP]. For these we could precompute a list of possible 2-psp instead of sieving.

5. Fermat test.

I think this will be faster than SPRP + Lucas.

Any thoughts?

[QUOTE=CraigLo;586706]

The algorithm:

2. Precompute ord(p) for all primes.


Any thoughts?[/QUOTE]

In Perl, the function znorder is quite quick. Up to 2^31 the following Perl program was run on my standard desktop in 304.5 seconds, suggesting about 12 minutes for 2^31.5.

[CODE]

#!/usr/bin/env perl
use warnings;
use strict;
use Math::Prime::Util qw/:all/;
use Time::HiRes qw(gettimeofday tv_interval);

my $start = 2;
my $end = 2**31;
my $starttime = [gettimeofday];
my $x;

forprimes {$x = znorder(2, $_);} $start, $end;

my $duration = tv_interval($starttime);
printf("Execution time: %.2fs\n", $duration);


[/CODE]

[QUOTE=CraigLo;586706]The algorithm:
1. Find all primes up to sqrt(N) = 2[SUP]32.5[/SUP] if we want to check up to 2[SUP]65[/SUP].
2. Precompute ord(p) for all primes.

3. Use regular sieve with small primes. I currently use ~10k primes which is probably a good starting point. This greatly reduces the number of potential primes that need to be checked with a fermat test.

4. Use the psp-sieve with all remaining primes. This guarantees that a number is prime if it passes the fermat test and isn't removed by either sieve. This should be fast because p*ord(p) >> p. In many cases p*ord(p) will be so large that it will only occur a few times in the interval 2[SUP]64[/SUP] to 2[SUP]65[/SUP]. For these we could precompute a list of possible 2-psp instead of sieving.

5. Fermat test.
[/QUOTE]

If you sieve to sqrt(N) you can use a normal sieve, you do not need psp-sieve or Fermat test? Everything remaining will be prime.

I was thinking of another idea:
When you jump ahead, for example from p to p+1300, and test backwards until you find a PRP, then what about testing backwards until you have found 2 PRPs? (If first PRP found is still larger than p).

Most of the time those 2 PRPs will be found above p+1000 probably, and in case you get back to p in 2 PRPs and find a false gap, it will be double checked afterwards anyway.
At the price of 2 Fermat tests (+ any tests that are negative), we get a very low risk of missing a prime gap. What are the odds of finding 2 real PRPs so close together blocking a record prime gap? Probably near the square of the probability you calculated earlier? 1 in (8*10[SUP]6[/SUP])[SUP]2[/SUP].

But normal sieve to sqrt(N) is slow. That's why we do the Fermat test in the first place. The psp-sieve should be very fast. Then we only need to normal sieve with a small number of primes and do a single Fermat test to prove primality.

Is my math and logic correct?

Using 2 different 2-PRPs should be much stronger than MR tests to 2 different bases on the same number. How low do we need probability of missing a gap to be before we can say we have proven a maximal gap?

It's possible the psp-sieve would still be faster than the 2 PRP approach.

I guess I do not understand why psp-sieve is faster. It looks like you want to psp-sieve to 2[SUP]32.5[/SUP] (except the first ~10K primes).
Even if ord(p) are precomputed, why is sieving mod (p*ord(p)) faster than normal sieving mod p ?

It's faster mainly because there are far fewer memory accesses. The normal sieve needs to eliminate one out of every p numbers. The psp-sieve only needs to eliminate 1 out of every p*ord(p) numbers.

I currently run in blocks of 36E9. If we did normal sieve up to 100k the first prime in the psp-sieve would be p=100003. This would require 36E9/100003 = 360k memory writes. Ord(p) is 100002. 36E9/(p*ord(p)) = 3.6 memory writes per block.

For large numbers near 2[SUP]32[/SUP] the normal sieve will still have about 9 memory writes. p*ord(p) will typically be close to 2[SUP]64[/SUP]. This is big enough that there is no need to even sieve. Just pre compute a list of possible psp for these really large numbers.

So instead of sieving with 200M+ numbers with memory writes in the 10s of billions we would sieve with maybe 50M numbers and probably under a million memory writes.

[QUOTE=Bobby Jacobs;583335]Congratulations on finding another gap! It is amazing that there are so many maximal prime gaps so logarithmically close to the binary round number 2[SUP]64[/SUP].[/QUOTE]

I decided to take log[SUB]2[/SUB](p) of all of the primes in the maximal prime gaps.

2, 3, 1, 1.0, 1.5849625007211563
3, 5, 2, 1.5849625007211563, 2.321928094887362
7, 11, 4, 2.807354922057604, 3.4594316186372978
23, 29, 6, 4.523561956057013, 4.857980995127573
89, 97, 8, 6.475733430966398, 6.599912842187128
113, 127, 14, 6.820178962415189, 6.988684686772166
523, 541, 18, 9.030667136246942, 9.079484783826816
887, 907, 20, 9.792790294301064, 9.824958740528523
1129, 1151, 22, 10.140829770773001, 10.16867211813223
1327, 1361, 34, 10.373952655370193, 10.410451351503994
9551, 9587, 36, 13.22143607744528, 13.226863716982413
15683, 15727, 44, 13.93691393843731, 13.940955875611515
19609, 19661, 52, 14.259228343849179, 14.263049081612024
31397, 31469, 72, 14.938339094975541, 14.941643713954356
155921, 156007, 86, 17.250455722905738, 17.2512512383879
360653, 360749, 96, 18.46025189899012, 18.46063586999309
370261, 370373, 112, 18.498183071287098, 18.498619405146496
492113, 492227, 114, 18.908630102645986, 18.90896427018037
1349533, 1349651, 118, 20.364028824642652, 20.364154964998352
1357201, 1357333, 132, 20.372202967479005, 20.37234327572016
2010733, 2010881, 148, 20.939290091967138, 20.939396277626003
4652353, 4652507, 154, 22.149529135616888, 22.149576890238947
17051707, 17051887, 180, 24.023412834966237, 24.02342806415923
20831323, 20831533, 210, 24.312251132247198, 24.31226567594332
47326693, 47326913, 220, 25.496150780051064, 25.49615748646031
122164747, 122164969, 222, 26.864252786761337, 26.86425540845062
189695659, 189695893, 234, 27.499111423558197, 27.49911320320056
191912783, 191913031, 248, 27.515875569415407, 27.51587743374218
387096133, 387096383, 250, 28.528116654614454, 28.528117586356245
436273009, 436273291, 282, 28.700655980036846, 28.700656912571894
1294268491, 1294268779, 288, 30.269489783877926, 30.269490104905696
1453168141, 1453168433, 292, 30.436554495809393, 30.4365547857049
2300942549, 2300942869, 320, 31.099577816119524, 31.099578016760077
3842610773, 3842611109, 336, 31.839439703844857, 31.8394398299949
4302407359, 4302407713, 354, 32.002496981951865, 32.002497100656115
10726904659, 10726905041, 382, 33.32051478290403, 33.3205148342804
20678048297, 20678048681, 384, 34.26738097180326, 34.2673809985947
22367084959, 22367085353, 394, 34.38065819502348, 34.38065822043679
25056082087, 25056082543, 456, 34.54444179308049, 34.54444181933634
42652618343, 42652618807, 464, 35.311915256759846, 35.311915272454314
127976334671, 127976335139, 468, 36.897086096100765, 36.897086101376594
182226896239, 182226896713, 474, 37.406944956835446, 37.40694496058811
241160624143, 241160624629, 486, 37.81120341206439, 37.811203414971786
297501075799, 297501076289, 490, 38.11410392914653, 38.11410393152272
303371455241, 303371455741, 500, 38.14229438999324, 38.142294392371014
304599508537, 304599509051, 514, 38.14812265783897, 38.14812266027346
416608695821, 416608696337, 516, 38.599901996646274, 38.599901998433154
461690510011, 461690510543, 532, 38.748135122042186, 38.748135123704586
614487453523, 614487454057, 534, 39.16059259801241, 39.16059259926613
738832927927, 738832928467, 540, 39.42645720880682, 39.42645720986126
1346294310749, 1346294311331, 582, 40.29213096779726, 40.29213096842094
1408695493609, 1408695494197, 588, 40.35749692819665, 40.357496928798845
1968188556461, 1968188557063, 602, 40.84000557906143, 40.8400055795027
2614941710599, 2614941711251, 652, 41.24991592650985, 41.24991592686957
7177162611713, 7177162612387, 674, 42.70655074661664, 42.70655074675213
13829048559701, 13829048560417, 716, 43.65276713583621, 43.6527671359109
19581334192423, 19581334193189, 766, 44.15454430119517, 44.15454430125161
42842283925351, 42842283926129, 778, 45.284100625854215, 45.28410062588041
90874329411493, 90874329412297, 804, 46.368938046534566, 46.36893804654733
171231342420521, 171231342421327, 806, 47.282940127218566, 47.28294012722535
218209405436543, 218209405437449, 906, 47.63270661562181, 47.6327066156278
1189459969825483, 1189459969826399, 916, 50.07922814332398, 50.07922814332509
1686994940955803, 1686994940956727, 924, 50.583377070516875, 50.58337707051766
1693182318746371, 1693182318747503, 1132, 50.588658751647024, 50.58865875164798
43841547845541059, 43841547845542243, 1184, 55.283148252391904, 55.283148252391946
55350776431903243, 55350776431904441, 1198, 55.61945307272224, 55.61945307272227
80873624627234849, 80873624627236069, 1220, 56.16651879039921, 56.16651879039923
203986478517455989, 203986478517457213, 1224, 57.50125113772148, 57.50125113772149
218034721194214273, 218034721194215521, 1248, 57.59733551004153, 57.59733551004153
305405826521087869, 305405826521089141, 1272, 58.08350519916523, 58.08350519916523
352521223451364323, 352521223451365651, 1328, 58.290487730302445, 58.290487730302445
401429925999153707, 401429925999155063, 1356, 58.477925784547146, 58.47792578454716
418032645936712127, 418032645936713497, 1370, 58.53639322594612, 58.53639322594612
804212830686677669, 804212830686679111, 1442, 59.48035496665738, 59.48035496665738
1425172824437699411, 1425172824437700887, 1476, 60.30584258713822, 60.30584258713822
5733241593241196731, 5733241593241198219, 1488, 62.314056782060014, 62.314056782060014
6787988999657777797, 6787988999657779307, 1510, 62.55768993488138, 62.55768993488138
15570628755536096243, 15570628755536097769, 1526, 63.75546100573405, 63.75546100573405
17678654157568189057, 17678654157568190587, 1530, 63.93864225213069, 63.93864225213069
18361375334787046697, 18361375334787048247, 1550, 63.99330792884274, 63.99330792884274
18470057946260698231, 18470057946260699783, 1552, 64.00182219536605, 64.00182219536605
18571673432051830099, 18571673432051831671, 1572, 64.00973762046758, 64.00973762046758

It turns out that there are 3 maximal prime gaps with a log[SUB]2[/SUB] within 0.01 of 64. Other than the 2 in the gap between 2 and 3, where 2 is exactly a power of 2, the only primes with a log[SUB]2[/SUB] within 0.01 of an integer are 4302407359 and 4302407713, with a log[SUB]2[/SUB] of 32.002. That is especially interesting because 32 and 64 are both powers of 2. It is an amazing coincidence!

Can any of the mathematicians here confirm that my approach (post #46) is a valid prime test? If it is I will start to write code to see how fast it is.

[QUOTE=CraigLo;586706]This might work ...
If n is a 2-psp (pseudoprime to base 2) and prime p divides n then
[CODE]n = p, mod (p*ord(p))[/CODE]
where ord(p) is the multiplicative order of 2 mod p
([url]https://www.ams.org/journals/mcom/1980-35-151/S0025-5718-1980-0572872-7/S0025-5718-1980-0572872-7.pdf[/url])

This can be used to sieve for numbers that are possible 2-psp. ord(p) is usually about as large as p so the product is ~p[SUP]2[/SUP]. This makes the psp-sieve much faster than a regular sieve.

The algorithm:
1. Find all primes up to sqrt(N) = 2[SUP]32.5[/SUP] if we want to check up to 2[SUP]65[/SUP].
2. Precompute ord(p) for all primes.

3. Use regular sieve with small primes. I currently use ~10k primes which is probably a good starting point. This greatly reduces the number of potential primes that need to be checked with a fermat test.

4. Use the psp-sieve with all remaining primes. This guarantees that a number is prime if it passes the fermat test and isn't removed by either sieve. This should be fast because p*ord(p) >> p. In many cases p*ord(p) will be so large that it will only occur a few times in the interval 2[SUP]64[/SUP] to 2[SUP]65[/SUP]. For these we could precompute a list of possible 2-psp instead of sieving.

5. Fermat test.

I think this will be faster than SPRP + Lucas.

Any thoughts?[/QUOTE]

I read the paper you linked and found the statement that psp2(n=p*r) => n === p mod (p * ord2(p)).

I created a simple python program using the wonderful [URL="https://github.com/kimwalisch/primesieve"]primesieve[/URL] and sympy to verify this on all psp2 <= 10^12

[CODE]
import primesieve
import sympy
import tqdm

LIMIT = 10 ** 12

def ord2_fast(p):
return sympy.ntheory.residue_ntheory.n_order(2, p)

primes = primesieve.primes(3, int(sympy.sqrt(LIMIT) + 1))
prime_index = {p: i for i, p in enumerate(primes)}
s, e = ", ".join(map(str, primes[:3])), ", ".join(map(str, primes[-3:]))
print(f"primes(sqrt({LIMIT})) = {s} ... {e} ({len(primes)})")
order = list(map(ord2_fast, primes))
print("Done calculating ord2(primes)")

with open("b001567.txt") as psp_f:
for line in tqdm.tqdm(psp_f.readlines()):
psp2 = int(line.split()[1])
assert pow(2, psp2-1, psp2) == 1, psp2
for prime in sympy.factorint(psp2):
if prime <= primes[-1]:
pi = prime_index[prime]
if psp2 % prime == 0:
assert psp2 % (prime * order[pi]) == prime
[/CODE]

This isn't a formal mathematicians sign off but I'm an undergrad math major and this is a moderate experimental verification.

I don't know about the approach in its entirety, but I can confirm the congruence.

If 2[sup]n-1[/sup] == 1 (mod n), and p is a prime for which p|n, then 2[sup]n-1[/sup] == 1 (mod p).

Consequently, if m is the least positive integer for which 2[sup]m[/sup] == 1 (mod p) [m is the multiplicative order of 2 (mod p)] then m divides n-1.

We thus have n == 1 (mod m). Since 2[sup]p-1[/sup] == 1 (mod p) m also divides p-1, so p == 1 (mod m), and n == p (== 1) (mod m).

Since by hypothesis p divides n, we have n == p (== 0) (mod p).

Now m divides p-1, so m and p are relatively prime. By CRT we have n == p (mod mp).

[QUOTE=Dr Sardonicus;588467]I don't know about the approach in its entirety, but I can confirm the congruence.
[/QUOTE]

Thanks. The goal is to check primality with a single Fermat test. The problem is handling pseudoprimes. If a number is a pseudoprime then there is some prime p that divides it. As you have shown, this pseudoprime has the form n == p (mod mp). If we remove all possible pseudoprimes by sieving for numbers of this form with primes up to sqrt(N) then I think a single Fermat test should be sufficient to test the remaining numbers.

Thinking through details out loud more time.

1. Sieve with small primes (<10K) marking off all numbers that are composite.
2. Perform Fermat (base 2) primality test

The set of numbers that are composite after 1. and 2. are PSP(2), each N will have at least one factor p < sqrt(N) for which
N % (p * ord2(p)) = p.

3. So we augment the first sieve by marking off mark off `i * (p * ord2(p)) + p` for large primes, up to sqrt(limit), this is faster than sieving with these numbers because ord2(p) ~ p.

Any number that passes that would pass 2. (e.g. PSP(2)) has some factor p and we've marked off all multiples that would fail 2. so we should be good!

---

I tried to understand what the saving in runtime of sieving by p=10,000 vs sieving all primes and I got a counter intuitive result.

From [URL="https://en.wikipedia.org/wiki/Mertens'_theorems"]Mertens' 2nd theorem[/URL] I believe the runtime to sieve number less than limit up to P is `limit * (0.577 + log(log(P))`

When I evaluate this with limit=2^65 and P=10,000 vs limit=2^65 and P=2^32.5
2^65 * (0.577 + log(log(10,000)) = 4.3e19
2^65 * (0.577 + log(log(2^32.5)) = 5.7e19

It says it's only 30% harder to sieve all the numbers (at which point we can skip the Fermat test completely).
Maybe this doesn't work in the real world because of cache behavior? Or because the sieve is segmented?
Or am I missing something else?

If [B] n=p (mod p*ord(p))[/B] then [B]p*ord(p) < n [/B] even when [B]p > sqrt(n)[/B], which I find a bit strange.

For example from the 2-spsp list:
6589845341971 = 485131 * 13583641

ord(13583641) = 485130 and 485130*13583641 = 6589831758330 < 6589845341971

But ord(13583641) could have easily been bigger, because often ord(p) = p-1, but I guess every time p>sqrt(n) then ord(p) < p-1, I guess that is why they are 2-spsp ?

Edit:
Here is a more extreme example:
137438953471 = 223 * 616318177

ord(616318177) = 37 << p-1

I think you want M = 0.261 instead of .577 in your equations.

I use wheels for the first 14 primes (up to 43) so they aren't sieved. I'm currently sieving about 10k primes so the last prime ~= 100000.

Using the equations for just summing 1/p
.261 + log(log(43)) = 1.59 (The actual number is 1.64. For larger numbers it is very close)
.261 + log(log(100000)) = 2.70
.261 + log(log(2^32.5)) = 3.38

The sieve from 47 to 100000 is 2.7-1.64 = 1.06.
The sieve from 100000 to 2^32.5 is 3.38-2.7 = .68 so it is about 65% more numbers sieved.

Small numbers can be sieved very efficiently in shared memory in a GPU, similar to working within cache in a CPU. For large numbers it becomes basically a random write to global memory which is very slow. I forget the exact number but I think it is at least a factor of 10 slower to sieve to 2^32.

Summing 1/(p*ord(p)) from 100000 to 2^32.5 is only 9.18E-6 so a factor of 74000 less.

[QUOTE=ATH;588533]If [B] n=p (mod p*ord(p))[/B] then [B]p*ord(p) < n [/B] even when [B]p > sqrt(n)[/B], which I find a bit strange.

For example from the 2-spsp list:
6589845341971 = 485131 * 13583641

ord(13583641) = 485130 and 485130*13583641 = 6589831758330 < 6589845341971

But ord(13583641) could have easily been bigger, because often ord(p) = p-1, but I guess every time p>sqrt(n) then ord(p) < p-1, I guess that is why they are 2-spsp ?

Edit:
Here is a more extreme example:
137438953471 = 223 * 616318177

ord(616318177) = 37 << p-1[/QUOTE]

This is a tautology. If p * ord(p) > n, then n doesn't end up being a psp2

[QUOTE=CraigLo;588538]I think you want M = 0.261 instead of .577 in your equations.[/QUOTE]

Doh, I used Euler's constant instead of refreshing my memory on the value and then I trusted that google's log would be natural log. Thanks for the updated math.

I made it up to 2[SUP]64[/SUP] + 2[SUP]60[/SUP]. I'm going to stop here for now until I rewrite the code.


I was a bit unlucky after finding the 1572 and didn't find any new first occurrences. I found a 1510 which is already a max gap. With a merit of 33.999 it might be a new record for largest merit that isn't a record. I also found a 1428, 1430 and 1446. The first 2 gaps without a known first occurrence are 1432 and 1444.


In total there were:
236 gaps >= 1300
17 gaps >= 1400
3 gaps >= 1500

What primes are these gaps between? I hope you can figure out the pseudoprimes just above 2[SUP]64[/SUP] so you can prove that the 1552 and 1572 gaps are really maximal prime gaps.

Here is the full list >= 1300
[CODE]1320 29.7556 18447459329282765737
1320 29.7555 18448829219040457859
1320 29.7553 18454478540221538011
1310 29.5295 18466554803229195359
1552 34.9844 18470057946260698231
1348 30.3858 18472480327246300711
1330 29.9800 18475043590195495411
1350 30.4303 18487242556245331903
1304 29.3933 18490370470062723803
1308 29.4835 18490772011307560751
1358 30.6104 18495386625134852093
1306 29.4375 18515975932358300023
1400 31.5560 18523860502690353989
1332 30.0232 18525269238564113911
1316 29.6625 18527673642419100563
1304 29.3919 18531125142517159643
1306 29.4370 18531291328025889811
1430 32.2315 18540962584206299801
1310 29.5266 18544511671978508351
1324 29.8421 18546410950300464289
1300 29.3009 18553984149844842289
1356 30.5629 18558795693605238191
1326 29.8867 18561507179142226753
1330 29.9768 18561650277851927143
1386 31.2389 18562939023748888207
1348 30.3822 18570208692452994943
1314 29.6159 18570980610550820273
1572 35.4308 18571673432051830099
1348 30.3819 18577753846792863433
1306 29.4352 18580498802224712911
1400 31.5536 18585472242082495913
1308 29.4799 18591692328938999323
1332 30.0207 18593969714690055769
1344 30.2911 18594661888957314289
1308 29.4797 18597742349322580253
1380 31.1024 18597959272110058339
1328 29.9303 18599916830188666433
1330 29.9752 18606222038326244701
1320 29.7491 18625271165295966133
1314 29.6138 18627768823076520869
1360 30.6503 18634423185915412261
1388 31.2812 18637042869569014859
1300 29.2979 18638146282920745561
1356 30.5595 18651050303787334787
1302 29.3422 18660009412653772001
1352 30.4689 18664669969746902897
1312 29.5672 18672143217315342511
1318 29.7023 18675019553256229921
1354 30.5132 18684637782563273137
1380 31.0989 18690479677730876881
1312 29.5662 18698382013591079389
1306 29.4309 18700838386670166157
1340 30.1970 18702776157152118893
1338 30.1520 18702903269397901513
1310 29.5209 18704096118826501199
1314 29.6109 18708814784483111489
1330 29.9713 18714319403633382637
1350 30.4218 18718711937520330493
1310 29.5203 18722164493314496777
1360 30.6468 18727303635686850889
1306 29.4299 18728960513026199011
1300 29.2946 18732992606702007493
1320 29.7452 18734911835253496507
1368 30.8267 18739755268272932011
1348 30.3757 18748267043976640543
1384 31.1866 18755454156088010929
1316 29.6541 18761850300342122387
1302 29.3386 18762244366849030297
1380 31.0961 18765583896243951373
1302 29.3385 18766661344665396559
1310 29.5187 18766785046142655671
1388 31.2762 18770964725085042581
1312 29.5635 18774247164112881589
1300 29.2930 18776778852749450653
1300 29.2930 18778124456695228033
1404 31.6361 18786155704257448033
1328 29.9235 18790923181898656379
1310 29.5175 18801181539765386669
1314 29.6075 18805710398510524487
1308 29.4718 18818176049793742673
1422 32.0404 18820374560835780301
1370 30.8687 18822442144590473861
1314 29.6068 18823301542727227439
1332 30.0124 18823986213966786311
1304 29.3815 18824947679223078257
1362 30.6879 18837197326537895029
1308 29.4711 18839764614043397909
1372 30.9129 18845276322469233991
1308 29.4707 18850999828560339509
1300 29.2903 18855485287170448909
1350 30.4166 18862575923971001207
1308 29.4703 18862976119663843109
1320 29.7404 18868898031379098793
1314 29.6048 18881523229505065639
1314 29.6042 18898060463916639487
1336 30.0997 18901547893221670273
1374 30.9559 18901604070365915083
1416 31.9019 18906417782503637233
1340 30.1896 18908376905326958597
1312 29.5586 18913682954134368457
1318 29.6938 18913897276280169013
1362 30.6850 18914392464334634639
1322 29.7839 18914653361409666941
1302 29.3329 18924315363794029261
1376 31.0001 18925135269128846441
1320 29.7382 18930897285504491431
1316 29.6481 18931454144446885931
1354 30.5041 18932856276003116023
1304 29.3775 18939449246969511077
1400 31.5401 18941712176050832981
1380 31.0895 18942853951027156697
1306 29.4223 18944892298746307783
1338 30.1432 18945905550854025683
1302 29.3319 18953103879571620277
1316 29.6470 18961575841147899461
1338 30.1426 18962371542242117161
1302 29.3315 18965221276361241239
1310 29.5117 18966254667762322499
1320 29.7367 18973425695070780253
1350 30.4124 18977128214158154347
1338 30.1421 18977924008811689001
1302 29.3310 18979055143256588641
1376 30.9976 18991800965398214171
1358 30.5920 18993820082037865661
1380 31.0876 18994114803239255423
1390 31.3123 19009310556649533931
1318 29.6904 19009990462733671699
1314 29.5997 19026321948268017857
1300 29.2843 19027029149997436861
1328 29.9146 19040176146870720533
1302 29.3283 19058621765699597069
1310 29.5083 19062578461768317599
1332 30.0039 19062981681715409369
1328 29.9133 19076491852343192471
1328 29.9130 19085500293424623119
1304 29.3724 19085950778747267297
1304 29.3719 19099684553641934729
1320 29.7318 19113349096661478299
1410 31.7589 19115439979543534397
1310 29.5065 19115629848637285829
1368 30.8126 19121671959415047991
1350 30.4070 19128614993851358419
1308 29.4607 19136390415224648719
1310 29.5056 19139319252512563007
1370 30.8570 19139673561594442349
1324 29.8206 19150457973054430597
1326 29.8655 19155002596239401923
1314 29.5950 19161775344455338487
1408 31.7121 19161929480853970081
1324 29.8199 19170887861939810587
1318 29.6846 19175157501926877361
1302 29.3240 19181194675951144141
1398 31.4860 19186695142062874369
1330 29.9544 19188315586033387579
1314 29.5938 19196457896617909807
1306 29.4135 19197570681692595133
1302 29.3233 19201873794209484881
1312 29.5485 19203894271650684499
1410 31.7556 19204280380463997521
1336 30.0887 19211610870882949993
1312 29.5477 19227112965111152821
1386 31.2140 19233763510542300911
1316 29.6369 19249740110814172793
1308 29.4567 19252814912564605433
1352 30.4475 19255850421800232767
1304 29.3662 19264261312702893563
1308 29.4563 19264638512992097431
1326 29.8614 19271760146943816443
1306 29.4107 19280055278537382691
1342 30.2209 19295728739477643589
1400 31.5269 19296598593740095499
1350 30.4010 19297477052264717563
1312 29.5452 19297525954695181621
1446 32.5626 19302599331311553097
1324 29.8147 19318354454349846367
1308 29.4544 19320447751259198911
1312 29.5442 19327708404440503087
1368 30.8052 19329172146660392311
1328 29.9042 19336285497188129051
1352 30.4445 19339481763653702897
1302 29.3186 19340280692260184299
1344 30.2640 19348276668786125717
1398 31.4798 19354145070075245459
1318 29.6783 19357522341968723509
1312 29.5431 19358457080938898851
1314 29.5882 19358611350344237557
1312 29.5431 19359998190237606439
1302 29.3179 19360037750484266221
1304 29.3622 19381526967411550187
1390 31.2986 19383460630325284327
1300 29.2720 19383806852581672231
1344 30.2626 19388213893853781503
1316 29.6320 19391885476543253291
1412 31.7935 19395452773072642859
1330 29.9471 19396577602405279999
1312 29.5416 19403877497829517009
1328 29.9018 19405229325309807929
1356 30.5322 19406725210976520173
1398 31.4777 19412217547443523213
1510 33.9993 19416933154878124507
1320 29.7207 19433441013907883071
1384 31.1613 19443488652805011547
1300 29.2697 19452392062379948941
1308 29.4497 19456362957031103833
1350 30.3953 19458788103284018719
1302 29.3145 19459250344021440257
1350 30.3950 19465308267848886701
1320 29.7194 19469650123700816167
1350 30.3948 19471022981868510037
1324 29.8094 19471547461621304743
1394 31.3854 19472077714434602687
1308 29.4491 19475149746372751771
1314 29.5839 19481152993134313057
1302 29.3137 19483856608401059411
1300 29.2680 19503003471920075227
1378 31.0239 19507735355553017233
1350 30.3934 19511074360265466529
1306 29.4027 19513853413533166741
1310 29.4926 19519351498417757537
1338 30.1228 19522912418467196351
1338 30.1222 19540785923155089569
1360 30.6171 19552846690362495691
1312 29.5362 19560762200294155861
1314 29.5810 19568274701265434003
1428 32.1472 19572904592331377269
1370 30.8414 19576120611793417319
1308 29.4455 19579489015562287073
1300 29.2654 19581374041412544367
1302 29.3100 19591863996713195221
1334 30.0304 19592158617803080079
1312 29.5347 19603971670167723247
1308 29.4447 19604394082330840001
1332 29.9849 19605583029298732937
1370 30.8401 19613555266835812349
1328 29.8945 19617129231996799109
1300 29.2641 19618303414952687833
[/CODE]

I've written some code. It isn't finished but it's enough to do some benchmarking.

Using my standard cycle length of 36E9, it takes about 0.18 seconds using my old 65-bit code. This is roughly 0.072 seconds for sieving and 0.11 seconds for prime checks.

With sieving only, the best I can do with code that I have already written is 3.85 seconds. I'm sure this can be improved quite a bit but I don't think it will ever approach sieve + prime check.

The psp-sieve takes about 0.002 seconds so it adds about 1 percent to my old code. I'm psp-sieving with numbers with P*Ord(P) < 2[SUP]55[/SUP]. This gives 17.7M numbers in the psp-sieve. For numbers with P*Ord(P) > 2[SUP]55[/SUP] I precompute possible PSPs. This gives 28.5M possible PSPs every 2[SUP]56[/SUP] which is about 15 every cycle.

Interesting development Craig! Seems really fast and you already have found so many gaps with merit over 30, in such a short period of time, so interesting indeed!

Do you see this also practically applicable for bigger numbers say like primorial 3607#/210 with 1485 digits, or only in the range of 2^64 and upwards?

Kind regards
Michiel

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[SUP]80[/SUP].

How far have you gotten in your search now? Have you found any new large prime gaps just above 2[SUP]64[/SUP]? Have you proven that 1552 and 1572 are maximal prime gaps?

[QUOTE=Bobby Jacobs;600956]How far have you gotten in your search now? Have you found any new large prime gaps just above 2[SUP]64[/SUP]? Have you proven that 1552 and 1572 are maximal prime gaps?[/QUOTE]

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

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

[QUOTE=Bobby Jacobs;605422]Well, Craig has not been on this site in a while. Does anybody else know how to prove the new maximal prime gaps?[/QUOTE]

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[SUP]64[/SUP] to 2[SUP]64[/SUP] +2.33 X10[SUP]16[/SUP].
As far as I know ATH had checked up to 2[SUP]64[/SUP] +1.05 X10[SUP]16[/SUP].
The first gaps that are still not known to be a first occurrence are[LIST]
*1432
*1444
*1458
*1472
*1474
*1480
*1484
*1492
*1498
*1500
*1496[/LIST]. 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[SUP]64[/SUP] +2.33 X10[SUP]16[/SUP]. then it will be (hopefully a new maximal gap.

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