experimental-projects/pseudoprimes/programs/smallest_superpseudoprime_to_the_first_n_bases_cached.pl

#!/usr/bin/perl

# a(n) is the smallest super-pseudoprime to all bases < n, but not to n.

use 5.020;
use strict;
use warnings;

use Storable;
use Math::GMPz;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);

my $storable_file = "cache/factors-superpsp.storable";
my $numbers       = retrieve($storable_file);

sub check ($n, $factors) {

    my $gcd = Math::Prime::Util::GMP::gcd(map { ($_ < ~0) ? ($_ - 1) : Math::Prime::Util::GMP::subint($_, 1) } @$factors);

    for (my $base = 2 ; ; ++$base) {
        Math::Prime::Util::GMP::powmod($base, $gcd, $n) eq '1'
          or return $base;
    }

    return undef;
}

my @table = ();
my $w     = Math::GMPz::Rmpz_init();

while (my ($n, $value) = each %$numbers) {

    Math::GMPz::Rmpz_set_str($w, $n, 10);

    my @factors = split(' ', $value);
    my $v       = check($w, \@factors) // next;

    if (defined $table[$v]) {
        next if ($table[$v] < $w);
    }

    $table[$v] = Math::GMPz->new($n);
    say "a($v) <= $n";
}

say "\nFinal results:\n";

foreach my $i (0 .. $#table) {
    if (defined($table[$i])) {
        printf("a(%2d) <= %s\n", $i, $table[$i]);
    }
}

__END__
a( 3) <= 18446744073709551617
a( 5) <= 18446772946775551381
a( 7) <= 18448213885892406001
a(11) <= 18446752100793694681
a(13) <= 18451828372234257001
a(17) <= 18449374705244374321
a(19) <= 18465639305360607361
a(23) <= 18451080445758779521
a(29) <= 18571582148726098801
a(31) <= 18471479627709108001
a(37) <= 19002174365256929281
a(41) <= 18485982321819566401
a(43) <= 18613287659885992921
a(47) <= 20106242479131492421
a(53) <= 18608193618187380481
a(59) <= 22416542344024395661
a(61) <= 32718347134218243361
a(67) <= 5503472548299991044361
a(71) <= 33531459396238264930561
a(73) <= 1501102626404084178094242888697104636583180360801
a(79) <= 834968576047116550943126161
a(83) <= 504034994367276175569791376316904843521
a(89) <= 1605821861501903391928475971847689791140852250844973917340221
a(97) <= 21150412877533909683421
a(101) <= 4252514909097506677574369666445434514158341496423426614528887464825381284201
a(103) <= 27868071136368885227460500328787679297366597981179701917430159821864341
a(107) <= 22353231034997821856266316140256635765390616679943070766056715401582561252446678141
a(109) <= 707661006022916086215150856193184757479853944131105830920721240383377827045381
a(127) <= 345833571714174072817436649641162397701375497826071918049409530434186302180259117666857284033094721
a(131) <= 56402590653088301077104128140441056725705101531554510867404623123553410598393277720632173924367761
a(137) <= 25195482383584166027553492358521330937717621869138905635600725327857150482687134421
a(139) <= 3682318342234638288515006394642695721940652474022258481688403648082636141169301681858952148935937013421
a(157) <= 1697762401495461048304564138320829485319626753977025682911237443534470119787774190154237286893038287299544616969641
a(167) <= 17741088068274649883036611721313574578411309604089775456157383534536258723141663282543785193734833789120196872288269974903941
a(173) <= 237684684003246999851535464441120620046191830335593588265246886892813088726079864031907722253554103727805564682988252305036807471409855181
a(179) <= 13227321796806350208949914773851520275992562156622353210144093979909542327177210578860692034580174659401339780617408513212291818762981
a(181) <= 6416307725342807226749660811178329083979137226812335337293080454694069962208026506700356902560852543571028738464062449829744994331734073424201
a(191) <= 111151014180205929039946951800910922458788676408030945362352719965858937205888768927363329738128108589034209912889628042773333999132995131631067501
a(193) <= 67343750780981270680830649780746147152711454984284321871097733205508675130418098404365275204151536933148960290956969851208960345606703788219006236144327061
a(197) <= 3091372621718797502604231042728271770426488122703631738286119455057447446243049263359995382511468288693578583996897597337874252305712666381881
a(199) <= 230865710743709419935525839782213943760559703485835536954864624338010684826549842031266892654990000976406934931426572428042535404684240239791781734757214020541
a(211) <= 11061317738583480096639286810009803633831557447631841177384371859177600823992063671874263452843914428311774434556733287567473339125073585887930418100664854384614201
a(223) <= 955595313412822452049711447334728879572664886935810951776434651911519732831666235706759256251228055611606959612161090858128248719989166485772769784801048644293964079031026601
a(227) <= 103165289958241444313121909314300321896722392895723263977496720583917130340398252793648548614865885212816489951082786331562611755436282549679684266713518066785540638714429541
a(229) <= 6974976675972300458304022130575670866322786313621184345766975046686094873769892768732549703929220214149846249658703710031793198339321592803337605704221
a(233) <= 140933159579892122379633248310120612561025067322614840246911838072174779962718055845530718829033933453594664954765844755377880964041427901224489266002890880788492411378594660229201874970801
a(239) <= 6991332978333078219700401429599165098326884021520624616380895107671315014266240745560315204725650520574261913134252768382896321765092806593535835144104417269412577863660723024953486624661
a(269) <= 145063492844124994866230113790934841611167178675455834332878674341711567199035169601462054809085089342187226156408486462755332628385861814666068151172824707014831369781121339960827756612596187311739427791004449014181
a(293) <= 24008779916958534577665966001575216432477607689877861393729175459017050501973131297708775353028370572583274916029887337593597442906237231008053552076433448362600628196679016495948603465519947056687260561229690011743366135347461
a(311) <= 72764927477603128144477897328831064932215799960916922259159249809068265973289889885798883465224701985517928236419296738612270850545010786581606335782441280797088831943059263914332212288100346327652499208574602795862666027026583502155783224567443593441
a(317) <= 341674001139066715456108363988919604090663751614685389098879779713565358800148747271946724656797078645954139059482470475107859108764912667702917664357417730296206259179741621456108600077773467543830844796192524417133605620568412697593386022056257276113516202021
a(349) <= 188102855864420572763612382762201079740869609145951014005216688534201415094249193598720424096693059592701978846963449209509863740781114207451469497573574025934465978450983471952585467903293681942943424789096984044796676803071611142814263367289619442948522814836301502152739341
a(353) <= 2189013735433014099318874149920956442603410302931263003705438721961114923396432798070384704079108509039338687402043132907488848706624423009230961976400013704156513291981058203434653818604522009719448243408647090016049401493770767438742566065637594413391454056125363429508153818745241
a(383) <= 1003897692639671941879119189386451474858323468572096628951296839192632250247802638346316122093471820926057620004035290467308958800404655787192745179946326560833409756828456376577941258505236414632717631846705274023940622240149444914328351655227149341939036043558040869114653988641059365080228048704422991509564761
a(401) <= 465538181939351773363713110572534572622107611262656627656878072362275673218551138626566749249357902912753378246968538759929190007481040618212807152120551750986238263515413219634750056352103303408308973862283847936047301771230414871940098696693933233669815627299977493588058756614820945541962195761710758532812674902178172230501
a(409) <= 1862152727757407093454852442290138290488430445050626510627512289449102692874204554506266996997431611651013512987874155039716760029924162472851228608482207003944952962521021053603839793595259808320154037283041455988587631832739247630235007949168505835209548019210123314392587786489609503304443967088525724933149386791085513461001
a(431) <= 3858196868729471060963042608359381682726441549154463942888042371948162026317409452518757478947360020141321147153108524465214959846760398269352223710130895594735652154793138954995286115675379639304455571990729471961459231333432262291470265850641402525579439489194907883376941943969594177700893862338236866388673912565383380036415389859978871280829041
a(487) <= 134667958813505595733403612692487277030499738559145617886689475156527366258754356106361783444150227504354734101413322728658933888097680897013907339719436421756289300518246258072412755740439363485666744790551577529980908220856918626460825071608007518691076320758556013365217646835280842136271308251743995192999844336110402890152486901946049695520785819806611727882290480192930849020682443160332466612721
a(523) <= 39245798381418572422858536610382911610699530186285599800123491373031309359209502099508809206759907465949850090405096957231156011275420722178019615743616610083068098634695370889922106597920883947890459774404783848360932255318427805933733717304060732899647338210974063053121403523818219180040156092526773276157627568575215888927674249088597714349246978425533458170661805236013235928090774640522475331537287590112356557470090991937417541
a(563) <= 85474748242379385366094816268973624888150242213226622180749138318386315935863212081942773317297904345474600957207428590062778602152519956800727219132027890643383467070099011582284945709124001108514764722966245494493169941622314836646386558535398146857006553207552461902964756053556805850282748662504578139090961477044287402823322355055911488039369571766331538282989461368172866093039969460784972736481613017667409050543252201255683285242294097740381698721
a(587) <= 819940925028025550708049598425885299394834759842119346918687094798424595905582884572324879300908079706039049190001584945067885244298353574796173588004748258835805639260986448104831802694642641034978922628932951812432648153344150005383958861098564625759934673101623123315845338788147281755679973991997858888902912756390279201137429818528301658320858691450496660075536285556756483758710640498986275618316420063119225425199548828923872380534628375369549574381
a(601) <= 500732880375785035577877989756350328323378170745353062589019102119496773476438677582705271318705022832885091075962800873261434757633186184296439835444295038531868929684184499913691935395227647116138586575772499728682926879673246407688051205915760379803587292006203099881396805145632121126566661120762241847221060267034000524626841242613098282766387880120990326336091968698335618143734844886904102593037014970417588057227176827006229369283528310761562594146598294917065799522308551949441001
a(673) <= 1099464257019343060928718304711006552400211260778519845730402742549722951418511795099810572291188817274871976098485057108124746655680990660536521961529246259684166606215090287135427926112521425772978904326751727648360455825985462378607470680010663921811227328279034034396068348663633863158204688217622115922057446388869696530950731949154390288452362288288734339766225709283400766943012766708371611615377666263363886169494431368334450620689806266568793354206836691808511032915946180966039159552924981898625552311745650463339929821547019282483315658263703601
a(677) <= 3481241445533323182699717466932249248831070497481341965798103054253983535326079544465735370761543455171065664943649122335656736725662654626482463228756882975540560611100933240793811227877132952416572131640849368573062832318818359251209723285582077636899430643678532886723325541964506992954744440935261696693648677594263552406987266168836908185440711839991046784190334585533408177066652280847998740116843155161933425406833875791153397490399048633049087339686357989809428850000171219820346462625847978990081372025305760743481655230302744738002085506162903800153570443201
a(877) <= 405561311707611058981545239095418621653608407671158063399641608211914472850997543094341189115703670821304978679058509036796826560813096864915178475502591648497190321756640326425542845966468078910262048950505582014548312235757445425879728347792488671631322233838281300966903472247953113718718151166981486149953586249036642429336742305723465627305884368034296072940706456063725457544902262873976472250908515219536183853921966751354493546970289791360272695721926572696086504715581014163631247714517066355580762986301687854742677895942767108591027747794661753633835226658915330095326839229636102535603289054281018203785189735170797742302222101493040196858009530563695827106893911078263625041114165554429470711469589459016140184363801
a(1163) <= 155409608113970679244344328576393659809843577345119457825433662937885814139461138118499140157134602680213283642514250614730762303171926624407110578412034352274655412073839733993782553101077197822185074139744786612253358690914922427061295000676094392046891747921491219425010962249202167904905413247671309630778366615594083717485882358604030522064156772351207743943349122006839546250988703060767098271638663183932204045821837741098807585980649223345728779925547957393405749568592484699204988934151761416975526483517920212956813947967392320953639138560378809046520859662827046242858970521043937765116269872151078221126494670103227981730945117213761226379975840495123501423495913649960024840191648901069033510358687131196104997364517455352525782408613975829900837933608974054687769311718396387405315112243312012726048958421878751899923476189223331885731936617173445622141186120020344683361281371691766970447227565018112202159099962228251616574164123108802856406247780048534363761
a(1361) <= 96566332176631433004274685026745313294622095028598179872095593543073272884378938772734256658586316158889601231808874533795245816580322740634992471607023302628271766302906059348871518777985977120451894841412773956386520324270438592948428777282580180207868625157577086535369237733514797021078704604738085748736686374826911505907229216423931639835556439766368716658351696126161927503393011928005524606244614485693037163303074777928589086206010811188605482951446134176434121290461886350165255520374463496076622654297513448413105097943014475365898666322539228901229256284243986892831046131199204140411938008948830871596133087905284785807334655441890417600633351833069472851503630236056657619549016143398726067677196444087639603682827232814759711657279843108474538576136510437474269316345549142017309200102424106730658578331796897961883347711960481392076869541554338795468047083174527084398755918267259612872810940789413301051359814697308528620267725492664097201269892099615358957672895651035170787123419544326280130165327818232446246189822621805408519163006975144716955385621462272847176928243907146924799619912529541154270796522304478855941
a(1579) <= 7586387686100663065440358958346572538048632187906018619449774911681294470252275784525610914673571992232021096349047569920014508055876646052049758016594883535756654427316116630505175183603264713932651676616349866594140394303919889712359165620209322337222465799190514552321048345708141128769247430759254022850799527158602399093546073461849566016418752204575532814935032441737657576496963402192757217860909010651714067957540523393918262854117228954939221165259717892657340794469705599635721249612511288109828628245576555704852604738719221840097205235531150226995064091754262819204995767686704960956989357290100112686850133694074880961810782942475245342524922571472608413037160726814838205278431834155855083430220188391195630324268875421639556612379047140006616183935816649223653496556455692601549700702245426618207822010763487187882332272397660556059578614235041265516090450201209470984623312058351143985459538476341085968847236480908126280831639576722372615494126125554405512277270793002991603646501756010842624797112624151221722389770216390940543444879893050392084352040718944132419863256442305050776575974462088097196639464350061794585524926600838850142612558023561269691147474355367419522291707137533594486175519571557483039722690547811322430721263623596185854922413572129927287123477773130923167985568848649785611848835875832707081
a(1621) <= 3352320993318002378058846174074265840779637093097132191832777093128048396250211422369744223720177154229987922334129545162944409696598808592430196496215446599597953009323623829602834824259955925246217557464300791952811365700831253717302725854489215940770912497565944538631286120787753951043963077017958219080242842972544652026565715356235673412671083356126040898759311537221826595445306989286362586976522066402689019003983404528382501383021109375059988095765297450332686949170822202533586167905076511277462308364813365717446973114291825401903464317735184476194405839096517908134696062274795222978514938998582413860205536006269044522986363601473183680122240214277334209235158656184075943708844876289634730994543016392071741385366134305338931075336138322145579793173018802054160461604820047603102286175666823237074959775406760007512995014683145265255340600992783647587832541303874358901642779853708945294209989832873416664884693180352927681463299219079040821292300231729050681449020128941453253663812317238446093360628680296805284716038936274664206604708842605564698570397709950340697012151198206625891869135224563791922771567295650162881553781001397769707459796823050314263883110214151647153080324215195046805830949169047206070956096132314133222064774919228701686815103959646515628907043974931392288028107509786343739353095052366484080780623083129566316227399878018137293106878861
a(1693) <= 3331143441956480942766454187244937126592954826670484621300506356530299653951355177308712277339520201618055060719301715365408193093825657704979533533926125678325968389921772592543604663783515154343366027712467526227587328837086646297227097157186403390981930357196470160267405714635424956086228974754256983396511204494193529822721936527101336965715431184443856807948987769569645689112473216134109834326056439193581812546964828772344970137731179101261480026484184456593679054292739300471199565961160014321474704876544409018685008815308341672211184201526438808603862716192720965898625848756105992499437753836444527440712712332438093591483993556017928464046438129155683794775504617470664770342041579227372370793189100683000986112836898402321704691738880326403826673328131056999067962058986962389594894836365336752565140297764556311278992887627351461637832681227317030255846562466137126966836481335238849943518819749143434650612974189281163416657666022291253332275076205712176979095049342139420858244732347068315416051721510971398083404281488841595553080032378597113809699610309203198599222999031032069953608295092490728229293831332623348900139601255659934893600374001462232831899270164713762721519849294777083101910082948220907809361087201382190322515509503991409942615062185618169542738016649756673962236053191623798649643151600662883653080541646219866857805306943610938013461308452911996921568819132110681467831234427329488784937401
a(1873) <= 2162104185384868760222766600487776057619596506005414411561255467272422974108330138741297653903366388337389632761906549480737261014734568873117524850570735241453577993701745438747000450647416252832133436723761753457425896458888729449329393189264305263163633076805200961198933147998940420162635651278510929375310377029332337576413127790247045523839773353067073707815495970056744641372006751924264392985572467253361691712333718670922897891262334369051068448183493615963239985126859219914875333491341721136959297513310411774894010604427727821849141060256445593435331131434753005002263697104931464413912855569510158811956063151840378201518452787473395423362484624038623567368308578282494150893703978688298869924524366445445137286969994659587201995578848252906589000093014337055910651092249120309792802795713553258854015253924338625962277768734590049978877328637624162483821867409579173713464880913363173002477416335482469720955385592665863883623144678720576462757145494049733032814968892919673492533715848357803971232327726407777501122014985337442998035944372673962236438794835039657918355489031394127380643731115521168271319775597352258007015211027782931038928255707186359185485239342431209159207240284771276727865806498822013057544248158602270320424590854564865198816659132671547987862736083650131202658466950922845978604367904197276673669924269450537013941727563571007367011839862241958494294020691051347423484137925371081340358724517726882797326799024043854679731802320281759810626122690423064294004208987554332160583080552026858337895599043479688244189340241
a(2357) <= 48067833939279652105639146172099450403152056893845060980171102659306663169748997510949730775542531890007607453339938546638953284867528598017558348877734687850112621870628843869923769155403835971063919461090228015836319198994402988615086858990645260878210435938486749049071260292450528817091506718832851391023606895456615721837804810241595041888577679740410733567851078113666139504862771871984006857579557056686165436094010736339484605435327877699784451756289338927774156381883965550819258931993174112869372174320217069223501200435354307354252897479326292952354041368301442963872972247152364900060902903966812264487929567952843047990328471423750249182568509703998297914189525309951079650098798627852173554956273295583886762651178850456987333355958847822507023253119913398183758972419406866250340932169992853240402034631002022279325035096595318462081119142499173378379019687007512179558423180072770695933954754449453475413448476864794263069561395307359213617986730209370222850459183139020085566295255987964358619931736500177269263776796711078872606013455231192667436037981080635510516979707193081904228023852325448970838314931760220711369453537847100751450342488955684153374715202690881985094179625782460856258957942733732033691247837060855644113627410031158753831075721326799312694238593847012573577008807083947469892580236435899521146651574816845162314479746900907064109740953840381380095358572870164046373292073149323330594852477467598868125887730681795653919037784698310691345660784819911037308597075401706257964362263149542501955296723319230659848551447870628865870072016911269073989477339937534534045205957276229084712029799589458226109762594422589275816014601044347211100381927537249114714595097565080869709452335061287005202011501211408272622680998530305184608225358443809363597013056103120148251063084388586803998157320502761582180015315366297518427630221693516078038929215711377514649740442928622271431965469031393451758517987262474016222929237546154958675363579732382763900343115950851821
a(2447) <= 74720544188111489813409953159302631906779213675493741937833104002811247306201915571245562112042933564684238230336049606007506442157545300257654548192703986977564833141617132405611131077226972530634224879771331489277328504194972013848645674253188207729031210292832276965486493623466410780408187318744725336588996295576049096770419751891507707845635620321849177912541816032655079671729189712339966651690271119072984104651902548019327838715591615019859624377461818512447368047573381176652079885896034307686853013743666538583936434824489328896235474862054997337818179159173433127155213826204557745322673537051043162573185166405038016782124925146551474829968312902319149850151886648656139214400308579254768799899361645581746106033661132403312577282978176774834659484021970589562104551770992648567706852236354619278931484276469273000225091250209238764024980261277002152987394678767906487682741124015889551852239774040561887258382163426416321016317299244548431269540991366123980576014328562275470532694998512498550720698447758683380922729812892055546852131504254299044300054049936299596636793637781523294786935905608524828678560555919056694953269236720526567359916553499780047717411783784582284485910263127127302569545972434715141738517177800369186896001075137053198990291411875895804712236785522435427883193861464442440077093390018007771423122281541492894046205718258709678655263543619084478526149273614592843420902776239726794717500334730555597219109941167589442926473062138408515143669138219052165168997830018430215095811756068090981953431365362866696441687365192765069965762339265000478721970771925542497948885259987669444294925915012282665924388256090576902143058298285820008877508008697015860019792568732863514590082036475855505472739148942660923004512517524330573311174691372834097530202302084082935755862086049485687762540475706511814854315148286517592946113592903015034815809937178754466182043870602030753605888308968453691282708476452712456925408253780781967305073089800824393351711653804243041923756701017640015211224290772351835906968997599025777516323570595118127681