/
generate_williams_numbers.sf
130 lines (92 loc) · 31.5 KB
/
generate_williams_numbers.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#!/usr/bin/ruby
# Try to generate a Williams number: a number that is both a Carmichael number and a Lucas-Carmichael number.
func pomerance_condition(p, T = 1e9) { # original condition
# p == 3 (mod 8) and (5/p) = -1
is_congruent(p, 3, 8) && (kronecker(5, p) == -1) &&
# (p-1)/2 and (p+1)/4 are T-smooth
is_smooth((p-1)/2, T) && is_smooth((p+1)/4, T) &&
# (p-1)/2 and (p+1)/4 are squarefree
is_squarefree((p-1)/2) && is_squarefree((p+1)/4) &&
# all factors q of (p-1)/2 are q == 1 (mod 4)
factor((p-1)/2).all { |q|
(q < T) && is_congruent(q, 1, 4)
} &&
# all factors q of (p+1)/4 are q == 3 (mod 4)
factor((p+1)/4).all {|q|
(q < T) && is_congruent(q, 3, 4)
}
}
func non_smooth_pomerance_condition(p) { # weaker condition
# p == 3 (mod 8) and (5/p) = -1
is_congruent(p, 3, 8) && (kronecker(5, p) == -1) &&
# (p-1)/2 and (p+1)/4 are squarefree
is_squarefree((p-1)/2) && is_squarefree((p+1)/4) &&
# all factors q of (p-1)/2 are q == 1 (mod 4)
factor((p-1)/2).all { |q|
is_congruent(q, 1, 4)
} &&
# all factors q of (p+1)/4 are q == 3 (mod 4)
factor((p+1)/4).all {|q|
is_congruent(q, 3, 4)
}
}
var primes620 = [5003, 5987, 6563, 9803, 10427, 11027, 11867, 16763, 19403, 22283, 22907, 24923, 25667, 29867, 35747, 40427, 40763, 41243, 42083, 49307, 54323, 54347, 57203, 57347, 66587, 67307, 73883, 78203, 84347, 104003, 112067, 121403, 122267, 122363, 123323, 124067, 129083, 129443, 134507, 177467, 178187, 192323, 198827, 203627, 227147, 265163, 281243, 281867, 315083, 321947, 365147, 381443, 411347, 455627, 472643, 479027, 598187, 609443, 707027, 710987, 809507, 845003, 867947, 893147, 998843, 1051763, 1072763, 1074707, 1136123, 1140803, 1185827, 1195907, 1295027, 1420667, 1525067, 1558307, 1587563, 1784603, 1856747, 2042123, 2183507, 2191067, 2583083, 2689403, 3409283, 3525563, 3994763, 4015883, 4172243, 4274027, 4462883, 4679387, 4902587, 4999187, 5696123, 5751107, 5929307, 5933987, 6208067, 6245963, 6252227, 6302603, 6401987, 6671747, 7119227, 7326827, 7340867, 7390907, 7674467, 8072123, 8276867, 8479547, 8605403, 8695187, 8854883, 8972627, 9197003, 9462227, 9693947, 9700883, 10288403, 10352603, 12005363, 12137243, 12353147, 12551003, 12874427, 13700987, 13737707, 14472803, 15491387, 15619907, 16846763, 17182283, 17437187, 18123467, 18666563, 18789587, 19821107, 19852067, 20076083, 20657027, 21484187, 21750467, 21834203, 24449627, 24508643, 25174043, 25882667, 26344667, 27020867, 27819923, 28378787, 29371187, 29810483, 29978603, 32416667, 32604563, 33474803, 33622427, 33650963, 34130123, 34442627, 35306147, 35744243, 36012947, 37113443, 37516307, 38694347, 39020603, 39053123, 39086483, 39864347, 44591123, 45865763, 46729283, 47315627, 51003707, 51329627, 51479243, 52580483, 56976443, 57577067, 58395083, 59269907, 61672427, 62107883, 62888363, 63670067, 63766763, 66922547, 68926763, 70637027, 71362763, 71622347, 74854163, 77324147, 78350963, 79401923, 83650643, 93228827, 93275027, 94179707, 94716827, 95576003, 96704723, 100076723, 101681243, 102115547, 105058403, 105841403, 107300003, 108724307, 110852723, 112171523, 114333827, 114692507, 115781363, 115903427, 121262987, 123096203, 123454523, 126843803, 127047227, 130223147, 135536147, 135795203, 137093483, 138090707, 144305963, 146173067, 153352163, 153626843, 154026107, 155269547, 156242123, 157738283, 159113987, 165252107, 167805203, 172536803, 176518187, 179637083, 182093603, 184790483, 185355323, 193785947, 196234163, 196606667, 197161403, 197808827, 205489787, 206790707, 213347027, 221843123, 223346987, 231615827, 234059843, 240885587, 241917827, 244824563, 248527787, 252466307, 253791443, 257066603, 259049867, 264860987, 267636203, 271117643, 277523507, 279355403, 285624947, 293241563, 296891027, 300507563, 308603987, 312352787, 321965867, 325874267, 334969667, 336768947, 339011147, 342295307, 346595003, 354146603, 356656067, 357607403, 360582683, 361196027, 363729083, 373520363, 375424067, 379160003, 390670307, 403476947, 414422843, 415807523, 416531723, 423892523, 426490187, 426927563, 443363363, 450855107, 455230907, 457505747, 460015547, 461525147, 463876643, 473222507, 474692123, 477937067, 478958507, 484603283, 488253083, 501421043, 503639267, 514371707, 516460283, 549668387, 567413723, 576783227, 589857923, 610954427, 619177547, 631332707, 647050067, 671380763, 671775443, 689769467, 698198723, 741513923, 759563027, 760527323, 762596147, 765368867, 773410787, 785569427, 835549763, 846182243, 857011187, 879230483, 913547267, 923395787, 931271723, 941759867, 942577547, 948179987, 956779427, 968867027, 979410563, 983373803, 985607867, 1042057043, 1054536107, 1076958563, 1081879787, 1101930443, 1107852227, 1117127267, 1133485667, 1139255963, 1170554747, 1184969267, 1186597043, 1217688947, 1280799803, 1340255363, 1345056467, 1370534027, 1384129163, 1439565587, 1442558963, 1483832387, 1500979787, 1518523883, 1568588867, 1583134307, 1586152907, 1593956963, 1638246707, 1638279563, 1640450363, 1673498867, 1698578243, 1712121707, 1723037483, 1741472963, 1782299507, 1869339827, 1907889227, 1952265563, 1981211363, 1981686227, 2002702547, 2161363283, 2164332587, 2223821387, 2247384803, 2257182923, 2313900683, 2342335643, 2358285563, 2365924307, 2431111283, 2445382763, 2457692603, 2493548747, 2515505747, 2530852547, 2543139587, 2548304387, 2585622827, 2609674307, 2694000707, 2713215203, 2753719883, 2794046243, 2854921187, 2893877243, 2955515027, 2964009803, 2964577643, 2988618803, 3028146203, 3030236843, 3108495443, 3134256443, 3196293467, 3212474747, 3325160243, 3355611587, 3361707467, 3369832883, 3378789203, 3422391443, 3535300523, 3674441363, 3778275203, 3898069163, 3904512083, 3941727947, 3961815323, 3964367123, 4162171067, 4321112267, 4407440363, 4489950947, 4554695627, 4577360603, 4620088427, 4708691963, 4710995963, 4754130083, 4889392283, 4910078843, 4998584363, 5003629523, 5042545667, 5125415987, 5151593267, 5240243243, 5333689787, 5343444707, 5459704403, 5560240403, 5592303947, 5631606683, 5747783627, 5814384083, 5823545723, 5881089107, 5885109323, 6052388267, 6053200667, 6128580827, 6134338403, 6448080803, 6516763307, 6519138947, 6866836283, 6889292027, 6930553163, 7016120627, 7092744083, 7276231883, 7422712883, 7490008067, 7578493547, 7599012683, 7714374923, 7761591683, 7786043747, 8020986203, 8063123843, 8063438627, 8229446123, 8297435963, 8300117867, 8369939507, 8437088027, 8513676107, 8570641067, 8594608427, 8631134027, 8803105163, 8927440883, 8967039563, 9069641027, 9115211723, 9115855187, 9131776883, 9207476123, 9213008243, 9280410467, 9302901947, 9446845643, 9454452587, 9858736187, 9948847787, 9990625523, 9999012323, 10135853243, 10362267467, 10393347563, 10451207267, 10653747803, 10689483347, 10691597003, 10794517667, 11134161827, 11286550043, 11312941547, 11519200307, 11798205803, 11884439363, 12200325947, 12521956787, 12586462643, 12917675843, 13300058243, 13747853627, 13828077563, 13969017947, 14002976147, 14107702187, 14339106107, 14604332003, 14638838723, 14738355323, 14871859523, 15139602323, 15596627867, 16141024547, 16180934963, 16338933827, 16360973243, 16823182403, 16880215043, 16954379747, 17056960667, 17191871003, 17334273347, 17385021443, 18335189003, 18342030227, 18647320163, 18733506347, 19775714747, 19833840683, 20368490603, 20565105467, 20589672707, 21057947987, 21117748787, 21219047387, 21573284963, 22218640883, 22527606587, 22917099323, 23118302027, 23375098763, 23580332387, 23923588643, 23945201363, 24018493547, 24392140163, 24985186883, 25866345467, 26506168523, 27003107123, 27293562323, 27664318523, 27741985163, 28689361403, 28690012283, 28712103083, 28923095963, 29340641483, 29689750403, 29712899507, 29782788587, 29958583643, 30432597947, 31085005643, 31107483083, 31358465123, 31415143787, 31768665443, 31941266363, 32475836843, 32636181107, 32670887003, 34555999547, 35048520323, 35296832003, 35746771763, 35796377003, 36810435923, 37564142747, 37594450427, 37606204187, 37922832107, 38773348883, 39191947283, 41209653203, 41570885123, 41657960987, 41658585443, 41779795787, 42075259763, 42249648923, 42757295387, 42778691603, 43201394387, 44597952083, 44664257003, 44853972347, 45359601587, 45782696627, 46107829907, 46412869043, 46609601387, 46795294643, 46919227427, 48146296043, 49374402587, 49466006963, 49751734787, 49830414947, 49990649147, 50241747323, 50617402763, 50684708483, 50856202907, 51212522267, 51441771083, 53185590083, 53350350947, 54568358963, 54656463707, 55303780787, 55872613187, 56925121787, 56980887347, 57452276363, 57604693403, 58058642123, 59644363403, 59923040867, 60172250003, 61061968883, 61661532323, 62029379267, 62093447723, 62556898907, 63699450803, 64603919747, 64644871763, 64667429243, 67522523147, 68087211947, 68392313387, 68882171243, 69206712803, 69342422147, 69683830523, 69915194747, 71914894523, 74000769083, 74188243667, 74823927947, 75234473747, 76713317243, 77585913107, 78546193883, 79612442027, 81589719203, 82008857867, 82404490283, 83035387427, 84038101163, 84763405187, 85662176003, 87288931043, 87980005643, 88223306867, 89923686323, 90271937627, 90313967603, 93041693027, 93828985403, 95481516227, 95637508643, 95815522547, 96323604683, 97003443203, 97212896483, 97225612427, 97649446667, 98151599963, 99402680243, 99409344467, 99923410187, 100477976843, 101219449547, 102688601003, 102866924267, 103061359547, 104381380067, 105406472747, 105757693523, 106287312683, 107104329947, 107722167083, 108509708243, 111931116827, 112096143563, 112942222403, 116198253107, 117139713683, 118669446587, 122381441027, 123139241867, 125860941443, 129686499347, 130505375027, 136323616547, 137236352987, 144078692123, 144112553027, 145220447003, 151674980867, 157057740083, 157705095203, 164322518387, 167591475923, 170139940907, 170997917507, 174232764683, 174376550483, 178261044323, 178337403467, 181474997843, 181716358427, 183564155603, 186482787083, 188006855987, 188097317747, 190673527883, 196003489043, 198077690627, 200013846563, 200358727187, 202842865763, 203487797267, 205130303363, 207226320347, 207871567763, 213264316523, 214329465563, 215837440307, 216733724507, 218386460627, 219577306643, 223241130083, 225712966883, 226775820347, 228109213307, 231052848443, 231474062483, 238428504467, 239095981547, 239522611787, 240211407827, 242333626523, 244729690523, 251815959107, 253197504587, 254168076683, 257548609163, 260470414907, 266538452003, 269243581667, 269775359963, 270808117667, 275154292643, 281179860947, 287697646763, 292783804067, 295268933987, 296570177147, 297894166883, 305241543947, 307734569603, 308412920843, 320152474787, 324579617723, 325875351563, 330736658867, 341815929563, 341918171027, 342692788283, 343006290083, 344024701283, 345995082947, 351275193323, 357890740547, 358507800947, 360537447563, 366790292147, 367688833643, 381202315283, 381945133187, 391367639627, 393653940347, 394145274563, 397347839723, 403313415467, 410050919123, 414667642787, 415162028987, 415831263923, 423850193843, 427818906107, 428025528347, 429180667163, 430413272363, 432495257963, 433198584563, 434651995307, 435473314187, 436289270867, 439819408907, 442258478507, 443905148147, 445826046203, 451303799363, 454593262283, 462158577323, 463348308443, 467800826387, 473371037387, 476089881203, 483806996483, 488054739563, 491585609147, 492758265107, 494306767667, 498605667347, 499042902203, 500152847507, 501310383107, 501363158603, 502966754867, 504293193683, 511475588747, 518266418723, 521971349987, 522253666547, 527375567843, 529504598747, 534911108483, 540551833667, 541527928163, 543055226243, 559642230083, 571511485187, 600446279267, 603379559243, 607077919403, 617589344147, 618008321867, 626280474587, 626983355987, 628858189403, 633659633963, 641675992283, 677732986523, 678192782987, 691568479907, 705282671627, 706344656723, 706699143827, 710446286723, 712059512243, 719162705363, 726328494107, 727763057867, 734455978787, 736180055267, 746327700323, 756281607227, 758133126683, 779371277387, 792797117867, 805420338083, 814343332547, 815655075227, 824029836947, 825924486323, 840532074227, 840895046507, 842652530747, 843116449163, 849941922227, 853008584147, 857545289243, 858056950427, 863713501067, 864430945163, 866981421347, 875925661907, 906061773587, 938295978443, 959291106707, 980239383323, 986850768203, 999219432803, 1001353386203, 1002556667507, 1042202411963, 1060704003347, 1078234050563, 1080200570627, 1084477543043, 1087092730667, 1087123594787, 1088567910707, 1103543831843, 1111355799347, 1152132122363, 1154116410467, 1161112785587, 1178169476147, 1195925340923, 1217104108163, 1221121768187, 1233464151947, 1237123165067, 1238853505427, 1257897178163, 1269013593203, 1270679649227, 1295696932067, 1296901027547, 1298142023603, 1311542907443, 1316052108083, 1329187409987, 1331485579883, 1338954143603, 1360378850123, 1382417765123, 1389833015003, 1401228277907, 1412527990283, 1413277594067, 1413485664947, 1440603609827, 1469213662307, 1484391565403, 1509250206683, 1528471334147, 1550750402387, 1592957434163, 1609013101427, 1677109112843, 1691954303003, 1694156671283, 1695927494243, 1707964770203, 1709696200547, 1715140069883, 1746802611563, 1762438832747, 1764367920803, 1765018711763, 1765733907563, 1771302610907, 1917119954483, 1927252748123, 1982411103203, 1983446892587, 2047822976603, 2049515406683, 2108768893307, 2118321564587, 2118981915467, 2126231729507, 2195134794467, 2247245178587, 2261960474603, 2293949351483, 2294964431003, 2336075481563, 2385895946003, 2386495572563, 2446571849483, 2537739463907, 2722133536163, 2793076822787, 2795345465867, 2801567860307, 2836431147923, 2852325262043, 2880757904363, 2960783389283, 2976447958307, 3039800203547, 3065513512907, 3077795184803, 3106017135443, 3141844350347, 3146545727723, 3303999496643, 3313829031203, 3335889715883, 3350310368387, 3355617971603, 3379314480947, 3473422815323, 3485282353307, 3505950530387, 3624902059403, 3661271038907, 3670748734883, 3726920463803, 3768534197507, 3791312625083, 3863872180403, 3886559107763, 3909871577483, 3921104116907, 3963192553043, 3996312084827, 4018601356667, 4036824307547, 4118666801003, 4128944343443, 4160373693347, 4175078861483, 4259608479587, 4429747456067, 4478476506083, 4501744655867, 4502311050803, 4514009790443, 4558065649427, 4579875283283, 4601840961563, 4829532901643, 4879793874563, 4911628283363, 4955557838027, 4970468701043, 5123318768027, 5137273601987, 5357577765347, 5409242934587, 5415839352587, 5440983231347, 5482729057787, 5558457793643, 5705723135867, 5781908833403, 5792185812947, 6022337325227, 6025227910547, 6121382021387, 6198112277867, 6333519653843, 6380006277347, 6394402726403, 6556061823803, 6562385103203, 6578916370787, 6593735393363, 6757247086523, 6782132725163, 6825098551787, 6857721811547, 6868371552443, 6935079048587, 7089508736363, 7162721962307, 7306345780667, 7440087686723, 7522490825747, 7531954720307, 7554323185667, 7582770737387, 7651182540707, 7745439047747, 7775377415627, 7842430725923, 7904670066347, 7941923157563, 7978670549387, 8192183978123, 8209830953147, 8259105813083, 8286631580243, 8481086497547, 8613717425147, 8938801960307, 8944420602563, 9076559140403, 9096576003227, 9219793002083, 9254810718467, 9292443749027, 9343441114307, 9361915665563, 9540337531427, 9674513510507, 9685255163147, 9688352206763, 9826720820003, 9959251126523, 10020563196467, 10047976765067, 10048608565883, 10091907996587, 10129909677947, 10142885853803, 10227534612803, 10295586301643, 10360065250883, 10364753829587, 10388318665427, 10400813054243, 10681706954027, 10742815880267, 10869505984763, 10900201957523, 10934495759123, 11211493371707, 11316247908443, 11329659315083, 11382923254643, 11441423775107, 11509475679347, 11570508049187, 11619092274947, 11706343315883, 11726422907363, 11764893056003, 12238205854907, 12249904453307, 12254837741747, 12463082133347, 12725326040507, 12949841371043, 13101796392107, 13103787884387, 13255898179787, 13571566517123, 13652879923547, 13743931311323, 13755001916963, 14144547460427, 14179029470027, 14427616013747, 14552069753603, 14827357763963, 14954888982347, 15161143183763, 15287891623883, 15311568641723, 15467314209587, 15495765291803, 15656573431547, 15760693624667, 15849308230523, 15854754991547, 15887762832563, 16004324745947, 16040331525203, 16084064843387, 16242898903643, 16405715580587, 17028415047563, 17290895168123, 17426441003267, 17588265716867, 18254656170827, 18314753553683, 18884008226123, 18962013223787, 19022254104083, 19082007788507, 19434054532283, 19689978232187, 19774780091483, 19937455896203, 20453821551827, 20671588148987, 21217226920907, 21462127223963, 21744381856427, 22472347939667, 22814410039307, 23077926086723, 23093636218883, 23138093384843, 24217748762507, 24966673160963, 25181979646427, 25269245084747, 25436779902827, 25513833729827, 25939374193907, 26950529333867, 27430893278963, 27433051197947, 27478158745883, 27995244090347, 27998600149547, 28111138628747, 28264851805643, 28558820279723, 28799022467483, 30030651188723, 30117259892123, 30321016458347, 31551033516803, 32369868797507, 32479468525643, 32687225459027, 33067009392227, 33425312567723, 33566165185307, 33851251809443, 34579652792123, 34751356594523, 35630843544323, 35918538773963, 36323149965227, 36600713556923, 36763326214163, 36765194669243, 36859970583587, 37988454215843, 38848563885203, 39328340621723, 39801554148827, 39876319505987, 40280716723547, 40418257493987, 40460293395227, 40463928189227, 40853630623283, 40980393954587, 41469439917707, 41634467037203, 41988809964947, 42710425439987, 43091033488907, 44199623457107, 44208600403043, 44392892480243, 45214211159963, 45605226380003, 45747135119843, 46153132695347, 46514026762667, 46554518348747, 46723263972587, 46739187917267, 47369169281363, 49075380599123, 49277047241267, 49519594020203, 49693346789147, 50657706647987, 51084356425787, 51868980758027, 53524274838347, 53725579892627, 54344643015347, 54585395516987, 55066584524363, 55220904946787, 56159214828947, 56528255403107, 57703608585083, 57986601434243, 58011282472547, 58055027232443, 58085406024323, 58595065221923, 59247642174563, 61003876810907, 62646030831563, 63484756628507, 63940625647667, 64847471815283, 64866633320747, 65372742123443, 67218452863307, 67393499486147, 69657154063307, 69816842799827, 71755383731363, 71903087679947, 76753513980107, 78195909340427, 79072665506603, 80889030232547, 80907674130827, 81961124494787, 82170666090827, 82477579727267, 82512682655003, 83918566007363, 84312963329363, 85017825914867, 85856369511443, 86871666384683, 88748852069723, 90761499519107, 90870201867563, 93033273964067, 93993849496907, 96834533603987, 98446668636707, 99551255004683, 100081876087043, 100309684136507, 100433656257227, 101213471059403, 101244754250243, 102205410482867, 102705330827843, 103732122165803, 104133850700483, 104176031151323, 104287827860243, 105253093034627, 105801589427603, 106035105636827, 106700314541867, 106874063173883, 107911507848227, 107956006972883, 115224896052683, 118948395977387, 120860723927123, 121815826783067, 122252895627923, 122387561455403, 123008411741627, 124392407571563, 126421753375763, 126936189944507, 127393284190787, 129267607064987, 129995179070963, 133188548898107, 134179888732427, 135616487040347, 137469089275643, 141013010179187, 141375024853523, 144230627902547, 144254468471123, 144531812139587, 154769388595667, 157125105378827, 164769782790707, 165754369026923, 166723317758843, 166883131585043, 170415343839443, 171633803051267, 178524279644507, 189395258903267, 191525461927043, 192287225086907, 193332330105227, 193468016586563, 195886884723947, 196575793998923, 201940235869643, 202298675949683, 209015721821507, 214278043870307, 215640850861523, 215883708797987, 219953270226227, 227053742773283, 229215549487427, 229648254616763, 231226614503483, 238427845745627, 243037883621483, 244323366527267, 244473627150827, 248429934021323, 248497900497923, 249208244104067, 249411536855387, 253367577523763, 253902200038787, 253919345073803, 259076542928867, 262858694831963, 264243123132587, 264497094927683, 265333595447267, 267791027437643, 267934269304547, 272829780264227, 278927270689643, 282841671209627, 285109823477987, 285951316285403, 290383597238723, 295221100358267, 300267023207843, 303637983271787, 309988160207483, 311201395777523, 314832107659403, 314991177652667, 318043273007627, 328813534485323, 334350409772987, 338038575831347, 338745870168803, 341683155136187, 346843236425963, 347245567890083, 359979202494347, 360679668865283, 364737641015723, 366357717044867, 369329285765963, 381150307254947, 381403229753867, 381962663529827, 384897844809323, 385559214556883, 386553120173723, 388453166085947, 392881118028923, 398289276206387, 398368406614187, 406477416390443, 408358865366483, 409937120891003, 411246391908323, 416471075861147, 434586909175043, 442615506258467, 444527917396187, 457884313171403, 464370024490283, 472156393842803, 482851512092123, 494039103065603, 494089269135443, 501911255266523, 505002688685267, 509321189046203, 522892208304563, 531145552587803, 533836952814707, 533973275772107, 553466720228267, 555219277716683, 558427819551083, 558711406317707, 561630157088027, 564657608583347, 572502757382027, 583110119102867, 588333795767387, 597184171441307, 597325750939763, 601132611478643, 603257010320747, 603421182689867, 605716136403947, 608721511540547, 617032338804347, 618248060417027, 618322175982587, 623959671285323, 645022608528923, 652112946998267, 660809694162803, 664656142888547, 678681420845963, 685177835011667, 691744278095027, 727028073472403, 735538049713067, 753599254597307, 760531495066643, 773127966513923, 780282675991307, 784454799049283, 796854246941003, 808348146672107, 833416832908427, 842557168108787, 843198010390763, 848609655132347, 871230814463267, 900772097527283, 919708815954827, 927282962390627, 933909122464163, 945112523777267, 954973489971203, 973616959049723, 976786130872043, 999183888454883, 1015170695639603, 1025185545528587, 1049142192182027, 1061514938720627, 1093664393343707, 1097209821479867, 1100247937039187, 1123865741920403, 1135644701881787, 1150713702023003, 1177808574356507, 1209634145420507, 1210070231072387, 1210188010338467, 1214874659305523, 1242657800952803, 1300393000972547, 1310423546669243, 1326166286896667, 1387038618621683, 1396592628314267, 1417068859020443, 1440342337943123, 1445364459801107, 1448391985610267, 1495713663430403, 1521207125511083, 1569693758717963, 1609972827806747, 1624444498937147, 1654042258227347, 1672824889599803, 1700010806378363, 1702668802430987, 1745771701384043, 1769411802386843, 1846664487998027, 1880418022028027, 1926424778152643, 1961097943845347, 1980478101623867, 1996018391680067, 1999911821728427, 2070488321013587, 2085054758121323, 2088262645010387, 2180915411922827, 2189422390531403, 2216307542171243, 2218516275145307, 2219414000274683, 2286764405381483, 2342969961676307, 2379732783470027, 2445934918896083, 2460691881833723, 2470932432917027, 2690997813743003, 2762254961702627, 2814589806558683, 2834363765334947, 2869535501850707, 2929172293317323, 2932577454014963, 2935854023789987, 2969213748336323, 3020818569551243, 3073673110706747, 3101371000200227, 3104849562515003, 3235238796281747, 3285815298164027, 3315161303303747, 3368947841039483, 3374982547293947, 3463360238101427, 3508731371470643, 3559625136261683, 3662373266422163, 3869311853707067, 3894122396803427, 4021855436339963, 4092334246001483, 4127045219115587, 4127816498745803, 4178487155887307, 4195777155959003, 4297612842652667, 4350902250536747, 4354702872331283, 4445385868576043, 4521311482843403, 4578809697819683, 4584399980277347, 4656482488678067, 4740220268428067, 4753230160843427, 4767239770155323, 4768318465377227, 4803981956525987, 4912275946718843, 4950233219804387, 5140463227973867, 5177154186574523, 5277936608002547, 5313508817995307, 5386560892100603, 5401510425664523, 5479062062615987, 5575361763719723, 5648459339875043, 5723737895914667, 6137401596884507, 6159802295032187, 6284420587607963, 6519831855735923, 6600316905303083, 6662683558988603, 6759712564297307, 6764580537823547, 6842873739207923, 6932302379792267, 7090323182194643, 7123896896797427, 7301837439873107, 7423032005898107, 7483685142532283, 7572010928000507, 7585210991707187, 7598318792034563, 7604488697514323, 7651923699830603, 7795299669308843, 7834545175010003, 7934360359558643, 8058082706175347, 8197408649073923, 8285341102435907, 8470328642519963, 8493684414768563, 8513468052684083, 8561200981449587, 8607491839865267, 8634933383942627, 8784707256866243, 8836569697022363, 8904054682585523, 8930920857479123, 9074525601051803, 9129829656292883, 9182724004227827, 9280412587535963, 9552203739121427, 10145286484466867, 10448013779960987, 10546884222902243, 10982573825805683, 11470847797382147, 11518275717582563, 11727660219060803, 11728190625795467, 11733906922970363, 12274184870022107, 12900124117888307, 13860804126519587, 14710317777427523, 14876404848807347, 15424852035191843, 15456233614284707, 15516182040130403, 15881251723875107, 15993559951849787, 16278199354365227, 16373247986319083, 16432225455935987, 16456981879192403, 17219972620249643, 17599336000468067, 17712183264506387, 17713242391363403, 17946824623023323, 18554485112684387, 18603905156978363, 18656807807083067, 19539078446270147, 19587941983265963, 20032994903640443, 20062739448254267, 20073762882803387, 20359633782746723, 20659400066441267, 20836233894557267, 21118565841067307, 21199872837863243, 21639863226002867, 21665921732653043, 21806240640021683, 21816982773446363, 21921768913642547, 22306424294890763, 22758386560600907, 23272156387715363, 23362136758549763, 23765686580141963, 23779912818978347, 24388673355443627, 25068477461488163, 25120668132244187, 28010077357379963, 28175136593318963, 28234760408801027, 28253421604483667, 28342894049307683, 28418793067182587, 28959000075093563, 28973635637593547, 28981865717066267, 29408837670188003, 30879024243546203, 31122911995061123, 34003034963387387, 34081016516391443, 34527755084118203, 34812554951408387, 35910014608004507, 36038400357251267, 36734225912784707, 40821325439590043, 43275561188284907, 45773909357813027, 45803392370932523, 46440190707594947, 46924172239098923, 48893432166202787, 49200142688511803, 49512050826222707, 49966879943561027, 50299228064987747, 50751627588104363, 50979565139595707, 51160874892711443, 51342043565115323, 52336515816096587, 53849090199502163, 56084293968300707, 56736105721363427, 57370939462458467, 59890538126188643, 62898373801967003, 63224830418726843, 63911087308130963, 64069860644436107, 65102211710974283, 65244956051352923, 68364114302945243, 68993625120758027, 69535625261957027, 70605691106667107, 70698154617852227, 74775688667115827, 77366514012572747, 77810517606645347, 81832868558259587, 84662170560167507, 85424126092904387, 88241901308943323, 88370577190598147, 89487944473229147, 90738049414775363, 92944479636891203, 93968413778246963, 94721650894464443, 98264729422537523, 100574867669404523, 105670092454526627, 106088472540298643, 107346675917023787, 109015944852075587, 110496757301649707, 119202335417867027, 120280161551631707, 123720497254227323, 123842703385128947, 139710885756410723, 142874667019602923, 144258585973273523, 148475293301464667, 149208771106892243, 150002901112328123, 151284810087833267, 155698225865750147, 156513316779821843, 158560157015337347, 159086994355643507, 161270234044769387, 182564686170812843, 185708623556971547, 186193009554484067, 186245783915355107, 187341391659000347, 193717105258811507, 209722418336488067, 214113212378603963, 217073524798507787, 219815153110441643, 221833965898638683, 222602612000153867, 228254762701474403, 234997175544575867, 242201050111964243, 243971856698516603, 245356346004186563, 249159259686463667, 258711794854487963, 267423977122819523, 271207705130884283, 288978492932019827, 291417082342436987, 302104887647400683, 313347078159591347, 315401630443322723, 321868979702422283, 325252632148305707, 332495942603426387, 342620644410625283, 353895843153126707, 374827336534364507, 374861765074159043, 378130477373807003, 392136195581446067, 453946097174059907, 468546146281174187, 475825128666231203, 488190214082668283, 513154194642154643, 523258024248646403, 523349974867018427, 542327418333492923, 547470795822983027, 547919001088955747, 555354140733500723, 572800553736798323, 573477691058513603, 580391299838820707, 580619268411606107, 587338419994431587, 608013369631893707, 643469090691644387, 648045186006733283, 690661450844434187, 694536474567709307, 695438444244168683, 709446148414434107, 715451685459108443, 757579277535813347, 771759984877375427, 818372340673892387, 834181931088858347, 862826575313833547, 881646446747895443, 904015626673291523, 917810275647435587, 926409902091049403, 957983612646444947, 970982876341566563, 988149678333335363, 1025460835415625563, 1135599215835240323, 1202488837681561667, 1202522950114508123, 1226454591140121587, 1283804986363619747, 1371063411574482467, 1374893187269319227, 1377484934835789947, 1395510653067507107, 1420738526009576003, 1440960146056135043, 1573938069761878523, 1658172557110780787, 1684876560586682867, 1725759802001944547, 1793205797680999547, 1798586889203203643, 1903210484910652763, 1930118566796892707, 1931107742142052427, 1943687942530023227, 1982956912291955627, 2045365290778092947, 2070575218629414467, 2128848802727382467, 2454907762770286403, 2881989581418653507, 2998963193285601803, 3057770866359333203, 3154852656683229347, 3243775175812344323, 3271649597763288587, 3293273341130047403, 3332003011782396563, 3379284211219592003, 3396033738339798107, 3668473736112124187, 4003282181723375963, 4104045934768959083, 4659174843785017163, 4756232973285560843, 4999420107398518163, 5384779401589724267, 5610619522633944803, 5630644485296016083, 5671974956911486523, 5732790094374343307, 5806713398544773483, 5968145502581738867, 6427261973867594243, 6622941681544599347, 6666972642646886987, 7006872751891625507, 7459916710490561123, 7712999766918759707, 8148134324527771643, 9518588067396692987, 9773976493068889187, 11377522503928924523, 11721529218605866307, 12418836529297484123, 14054980557432714203, 15257999331498847643, 15287120590231014227, 15808204622333584163, 16262625832371156083, 17176760531183413187]
func carmichael_numbers_in_range(a, b, k, callback) {
a = max(pn_primorial(k+1)/2, a)
func (m, lambda, lambda2, p, k) {
var y = idiv(b,m).iroot(k)
if (k == 1) {
var x = max(p, idiv_ceil(a, m))
return nil if (x > y)
#each_prime(x, y, {|p|
primes620.each {|p|
next if (p < x)
break if (p > y)
with (m*p - 1) {|t|
if ((lambda `divides` t) && (p-1 `divides` t)) {
say "Carmichael: #{t+1}"
with (t+2) {|w|
if ((lambda2 `divides` w) && (p+1 `divides` w)) {
die "Found term: #{w-1}"
callback(w-1)
}
}
}
}
}
return nil
}
#for(var r; p <= y; p = r) {
var x = p
return nil if (x > y)
primes620.each {|p|
next if (p < x)
break if (p > y)
#r = p.next_prime
#pomerance_condition(p) || next
#non_smooth_pomerance_condition(p) || next
#p.dec.is_smooth(43) || next
#p.inc.is_smooth(43) || next
var L = lcm(lambda, p-1)
m.is_coprime(L) || next
var L2 = lcm(lambda2, p+1)
m.is_coprime(L2) || next
var t = m*p
var u = idiv_ceil(a, t)
var v = idiv(b, t)
if (u <= v) {
__FUNC__(t, L, L2, p.next_prime, k-1)
}
}
}(1, 1, 1, 3, k)
return callback
}
var k = 3
var from = 2**64
var upto = 2*from
loop {
say "# [#{k}] Sieving range: [#{from}, #{upto}]"
carmichael_numbers_in_range(from, upto, k, { .say })
from = upto+1
upto = 2*from
}