smallest_strong_pseudoprime_to_the_first_n_bases_cached.pl

#!/usr/bin/perl

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

use 5.020;
use strict;
use warnings;

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

eval { require GDBM_File };

my $cache_db = "cache/factors.db";

dbmopen(my %db, $cache_db, 0444)
  or die "Can't create/access database <<$cache_db>>: $!";

sub check ($n) {

    for (my $base = 3 ; ; ++$base) {
        Math::Prime::Util::GMP::is_strong_pseudoprime($n, $base)
          or return $base;
    }

    return undef;
}

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

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

    Math::Prime::Util::GMP::is_strong_pseudoprime($n, 2) || next;

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

    my $v = check($w) // next;

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

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

dbmclose(%db);

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) <= 18446839241310879961
a( 6) <= 19391189202440697001
a( 7) <= 18512248848925882051
a(10) <= 27219515554681226197
a(11) <= 18469177082671932541
a(13) <= 25045621026961912651
a(14) <= 2382864270169911103621
a(15) <= 6799535555471931768317641
a(17) <= 20315155777788649051
a(19) <= 129713907272647698631
a(22) <= 2995741773170734841812261
a(23) <= 141175407400732532484464851
a(29) <= 407085840617715217573509253520046535651
a(41) <= 11968794224604718293549908104759518204343930652759288592987578098131927050572705181539873293848476235393230314654912729920657864630317971562727057595285667
a(43) <= 16293065699588634810831933763781141498750450660078823067
a(46) <= 1543267864443420616877677640751301
a(59) <= 122623673100774902819890811512093121818009864395929257382206929494220541500353599732762551419245399058398366502168963509640168639794202705645034115138272912046190084444976198156980059092407987735996562308131806635633617847615677949071026045920492821200676854540540234658043716124914438158326334228684623784307
a(61) <= 7901877332421117604277233556001994548174031728058485631926375876865078028180049751981627864304181541061183590498201673009039329539171539230651776950727307
a(211) <= 105216055594390884840438324972769319399722594046651360392070071794973423530188471087867855419188813164954561140227145977855514336985746250989366318940490798583710597151720075427387437940535767395296272532149397065590267303873620351321073058502920032770522836726669005262088263964215455869031740912313201227043
a(307) <= 2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867
a(547) <= 4755444900898962640570805079622407945513196432011911985648410022240088808985889200376095787527901239245756068158548164080646419498193938363223751878040975178651652955930683319090515589565114950046340315137578332784425652394857192999191244130079906060771897042318182261565231930157836276911534989784532752912947610193310744025493450293981924804993015182502555790249587996752315485361179895260300891395439822476185769523434215286135938029039660904526961670815522767096127450386003813203809365323894442795443565820952283705939380656438309180252554808691019535681908983623214664516034111470695703020642485875959651583213619466594932918476670651633816994599772548478768526764012575954414322984173288627
a(1009) <= 6941543021392713730431668387068999032987505813628626223678951265009922979171494889619620919629218172938050022712650390231108995307237169269667644098333312684776469399924110119789527532161256933656112818109620945798457804143586629828296071826627003328849527952336389650813108369731049080747183836913592892951933560765345204468790419691959105305515726737868378312872715843312320064073674571001295106119373097331445689095722655847864191050899780290639922180983329597857624757187701943317347314318342630851888782724340309365489828447876503970224596096163190175586664838655752084811432643865453475409306234610422754846201955355349982116992680801631254169733179214516679698471486732095757632702985749004267668618407596194879010235811205069773345370151540294560707067912911972617117872568917574563797510424723636252899372760040898527772334935423922327351299656281932266256675132502702322760435460536571309302586539469310861406622510368133332971804029286468542260235396204271045794929827474636467550655521103657096119618759746982193439030809406498947869770588717242290031299573971411197982166717351757954266001066384132372994264058429334563291496657469558139808375030168417007373133166391119553220773091860698215980720042621281779381114805103592526045494482900527480395872621990534353634675251867
a(1621) <= 106345207806296484231668043910066785399795652556314098984703724996175611913155370425059004666755351126370765757325069220154090475525113111331534155822504132427954121926028977897326016452032633264303162177531381326310998970713694521304856783427108211035837719173191888424497687716945903847840832601158220338315116311569353516661115745397618364437941836386218808101529448483687495168944238726821330736995943973596941803495501200742109710969089802656966120128959989924056907838239415947883597253487288911265130861076995785143322559232949628580082040985968381890859811544811963250166807225739883175758540592938038640525057077635260377283817570121188506720763322577723854603213904763949026451035886610117960695498777558294914095190286423434103595325322044355050505888390419892966130432853384420025991603809604285550077998959033403957562518661694503445321270371924756278334786001733438835926798599715925477942244937628383988529536076933049398733022131632892984494328799535905089231306547424707999668050846457897292105617153237859066140231207977706483096753560267776977308513770417672719215980272226316038096369457350381579229798547106736019854318870385754141371733858517502044218801634760265587498814280073328060552232702804872921969797735332629722017664747892121030708748712733180842486503682755515481434761547891191431690407378061063299887695616928512486921716155822944378708863947668462062195571745339003058779915940858554595239390172360173769656161537253021381577803596097455028941144286297184282046724577533468348343936096263977229393852616124982192888432604948830175933041671162863393593616389115022094081675889914163162852300506873558662214056728175728839204797446701664449699367321558065141345504373533192399722226922311408612622529245371708935701643178960931071329253928802738471610262504489056899252740549408250528391001108587552456472577625704595893048563596869581967781113019047808212452621728173827862405874506295664794063113108306419852891590636875366731732762664553725634243782507523770949879136684328870372364698244368287699980886402179469945231457642085062803806579094674257318340352731256782194724089323