New Maximal Gaps - Page 6

CraigLo · 2021-09-23, 18:19

Quote:

Originally Posted by Dr Sardonicus

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

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.

SethTro · 2021-09-24, 02:22

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 Mertens' 2nd theorem 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?

ATH · 2021-09-24, 06:10

If n=p (mod p*ord(p)) then p*ord(p) < n even when p > sqrt(n), 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

CraigLo · 2021-09-24, 06:45

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.

SethTro · 2021-09-24, 07:17

Quote:

Originally Posted by ATH

If n=p (mod p*ord(p)) then p*ord(p) < n even when p > sqrt(n), 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

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

SethTro · 2021-09-24, 07:19

Quote:

Originally Posted by CraigLo

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

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.

CraigLo · 2021-10-04, 05:49

I made it up to 2⁶⁴ + 2⁶⁰. 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

Bobby Jacobs · 2021-10-05, 20:18

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

CraigLo · 2021-10-06, 16:45

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

CraigLo · 2021-10-25, 22:43

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⁵⁵. This gives 17.7M numbers in the psp-sieve. For numbers with P*Ord(P) > 2⁵⁵ I precompute possible PSPs. This gives 28.5M possible PSPs every 2⁵⁶ which is about 15 every cycle.

MJansen · 2021-10-29, 19:56

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

2021-09-24, 02:22	#57
SethTro "Seth" Apr 2019 111101101₂ Posts	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 Mertens' 2nd theorem 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? Last fiddled with by SethTro on 2021-09-24 at 02:22

2021-09-24, 06:10	#58
ATH Einyen Dec 2003 Denmark 110101111010₂ Posts	If *n=p (mod pord(p)) then pord(p) < n* even when p > sqrt(n), which I find a bit strange. For example from the 2-spsp list: 6589845341971 = 485131 * 13583641 ord(13583641) = 485130 and 48513013583641 = 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 Last fiddled with by ATH on 2021-09-24 at 06:33

2021-10-29, 19:56	#66
MJansen Jan 2018 2·5·11 Posts	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 Last fiddled with by MJansen on 2021-10-29 at 20:04

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-09-24, 06:45	#59
CraigLo Mar 2021 59 Posts	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.

2021-10-04, 05:49	#62
CraigLo Mar 2021 59 Posts	I made it up to 2⁶⁴ + 2⁶⁰. 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

2021-10-05, 20:18	#63
Bobby Jacobs May 2018 2×3×7² Posts	What primes are these gaps between? I hope you can figure out the pseudoprimes just above 2⁶⁴ so you can prove that the 1552 and 1572 gaps are really maximal prime gaps.

2021-10-25, 22:43	#65
CraigLo Mar 2021 59 Posts	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 POrd(P) < 2⁵⁵. This gives 17.7M numbers in the psp-sieve. For numbers with POrd(P) > 2⁵⁵ I precompute possible PSPs. This gives 28.5M possible PSPs every 2⁵⁶ which is about 15 every cycle.