/
generate_fermat_psp_with_620_primes.pl
91 lines (69 loc) · 58.4 KB
/
generate_fermat_psp_with_620_primes.pl
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
#!/usr/bin/perl
# Author: Daniel "Trizen" Șuteu
# Date: 02 July 2022
# https://github.com/trizen
# A new algorithm for generating Fermat pseudoprimes to any given base.
# See also:
# https://oeis.org/A001567 -- Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.
# https://oeis.org/A050217 -- Super-Poulet numbers: Poulet numbers whose divisors d all satisfy d|2^d-2.
# See also:
# https://en.wikipedia.org/wiki/Fermat_pseudoprime
# https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html
use 5.020;
use warnings;
use experimental qw(signatures);
use Math::AnyNum qw(prod);
use ntheory qw(:all);
#my @primes = (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);
my @primes = qw(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 18990570901948665683 19424601827727592523 19446136417030749947 20021616827803179467 21508580852131788923 21712583176312725443 22319868786904952603 23811891485065963523 24335625721109885027 25667576698820885363 28119136750979534027 28778581223621774627 31179575422425923723 31805457664382582267 32048800053660230147 33301385469202933547 33609583816541973683 34958371361476721003 36797010991101076883 37837107119115295067 39960712541695314107 42594233069313285947 53124488079102901787 54436313269475606867 57458390828623213547 65318530118241733283 65935732681157937443 69203604098679896243 71253805272249312467 77615310528594222467 87231729687142377803 97494609888938325587 118787204331030171347 149783654928707474867 169046290814577523283 174739451001440889227 176021198853828547883 188825582091255593747 197675610583408730387 209822375767195448963 218515727134757195723 231239574705714414227 250997709850412900363 283417845636198816707 436854357849340155563 457160175195343015787 519145721217285286283 617373942999942504347 812190152340933363227 1131374128588340976947 1204537852186137098027 1494204424138930374947 2091686873470882434323 4098694483916743167203 4665648301718926194203 5360297573804957369123 10659431812315035515387);
sub fermat_pseudoprimes ($base, $k_limit, $prime_limit, $callback) {
my %common_divisors;
#for (my $p = 2 ; $p <= $prime_limit ; $p = next_prime($p)) {
foreach my $p(@primes) {
#last if ($p > 1e20);
my $z = znorder($base, $p) // next;
#for my $k (1 .. $k_limit) {
#foreach my $k (divisors(subint($p, 1))) {
foreach my $k (divisors(addint($p, 1))) {
if (is_prime(mulint($k, $z) + 1)) {
push @{$common_divisors{$z}}, mulint($k, $z) + 1;
}
}
#~ my $z = znorder($base, $p) // next;
#~ for my $k (1 .. $k_limit) {
#~ push @{$common_divisors{$k * $z}}, $p;
#~ }
#~ my $z = znorder($base, $p) // next;
#~ for my $d (divisors(mulint($pm1_multiple, (subint($p, 1))))) {
#~ if (modint($d, $z) == 0) {
#~ push @{$common_divisors{$d}}, $p;
#~ }
#~ }
}
my %seen;
foreach my $arr (values %common_divisors) {
my $l = scalar(@$arr);
next if $l > 15;
foreach my $k (2 .. $l) {
forcomb {
my $n = prod(@{$arr}[@_]);
$callback->($n) if !$seen{$n}++;
} $l, $k;
}
}
}
my @pseudoprimes;
my $base = 2; # generate Fermat pseudoprimes to this base
my $k_limit = 5040; # largest k multiple of the znorder(base, p)
my $prime_limit = 1000; # sieve primes up to this limit
fermat_pseudoprimes(
$base, # base
$k_limit, # k limit
$prime_limit, # prime limit
sub ($n) {
if (is_pseudoprime($n, $base)) {
#saypush @pseudoprimes, $n;
say $n;
}
}
);