mersenneforum.org New Maximal Gaps
 Register FAQ Search Today's Posts Mark Forums Read

2021-09-23, 18:19   #56
CraigLo

Mar 2021

59 Posts

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.

 2021-09-24, 02:22 #57 SethTro     "Seth" Apr 2019 43710 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 3,347 Posts 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 Last fiddled with by ATH on 2021-09-24 at 06:33
 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-09-24, 07:17   #60
SethTro

"Seth"
Apr 2019

19·23 Posts

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

Last fiddled with by SethTro on 2021-09-24 at 07:20

2021-09-24, 07:19   #61
SethTro

"Seth"
Apr 2019

19·23 Posts

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.

Last fiddled with by SethTro on 2021-09-24 at 07:20

 2021-10-04, 05:49 #62 CraigLo   Mar 2021 59 Posts I made it up to 264 + 260. 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·7·19 Posts What primes are these gaps between? I hope you can figure out the pseudoprimes just above 264 so you can prove that the 1552 and 1572 gaps are really maximal prime gaps.
 2021-10-06, 16:45 #64 CraigLo   Mar 2021 59 Posts 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
 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 P*Ord(P) < 255. This gives 17.7M numbers in the psp-sieve. For numbers with P*Ord(P) > 255 I precompute possible PSPs. This gives 28.5M possible PSPs every 256 which is about 15 every cycle.
 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 Bobby Jacobs Prime Gap Searches 6 2021-07-04 11:51 Bobby Jacobs Prime Gap Searches 52 2020-08-22 15:20 Bobby Jacobs Prime Gap Searches 5 2019-03-17 20:01 robert44444uk Prime Gap Searches 1 2018-07-10 20:50 gd_barnes Riesel Prime Search 11 2007-06-27 04:12

All times are UTC. The time now is 04:30.

Wed Aug 10 04:30:45 UTC 2022 up 33 days, 23:18, 1 user, load averages: 1.10, 1.30, 1.36