experimental-projects/pseudoprimes/programs/euler_jacobi_psp_to_first_n_bases_db.pl

#!/usr/bin/perl

# Smallest Euler-Jacobi pseudoprime to the first prime(n) bases, that is not pseudoprime to base prime(n+1).
# https://oeis.org/A354692

# Terms < 2^64:
#   561, 10585, 1729, 488881, 399001, 2433601, 1857241, 6189121, 549538081, 50201089, 14469841, 86566959361, 311963097601, 369838909441, 31929487861441, 6389476833601, 8493512837546881, 31585234281457921, 10120721237827201, 289980482095624321, 525025434548260801, 91230634325542321

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 {
    my ($n) = @_;

    my $p     = 2;
    my $count = 0;

    while (Math::Prime::Util::GMP::is_euler_pseudoprime($n, $p)) {
        $p = next_prime($p);
        ++$count;
    }

    return $count;
}

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

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

    my $v = check($n);

    next if ($v < 23);

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

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

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

dbmclose(%db);

say "\nFinal results:";

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

__END__
a( 1) <= 18446744073709551617
a( 2) <= 18446839241310879961
a( 3) <= 18449257951724194561
a( 4) <= 18446958624735295201
a( 5) <= 18451111612123159201
a( 6) <= 18497567256602491201
a( 7) <= 18467694226779169681
a( 8) <= 18456267871076452561
a( 9) <= 18688531265826428161
a(10) <= 18503336563379553601
a(11) <= 20198158760015248321
a(12) <= 18503425335804318001
a(13) <= 23316509180465462809
a(14) <= 18624497590495547521
a(15) <= 76078759212699843601
a(16) <= 308276471170043122321
a(17) <= 65364591090350724481
a(18) <= 25384545985392602648641
a(19) <= 47244286224922062276001
a(20) <= 3510976892390080715674801
a(21) <= 176430722557498388899032961
a(22) <= 299774827640366612231286196609
a(27) <= 51869154461968006838855041
a(28) <= 29960428950474953700369601
a(46) <= 105216055594390884840438324972769319399722594046651360392070071794973423530188471087867855419188813164954561140227145977855514336985746250989366318940490798583710597151720075427387437940535767395296272532149397065590267303873620351321073058502920032770522836726669005262088263964215455869031740912313201227043
a(62) <= 2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867
a(100) <= 4755444900898962640570805079622407945513196432011911985648410022240088808985889200376095787527901239245756068158548164080646419498193938363223751878040975178651652955930683319090515589565114950046340315137578332784425652394857192999191244130079906060771897042318182261565231930157836276911534989784532752912947610193310744025493450293981924804993015182502555790249587996752315485361179895260300891395439822476185769523434215286135938029039660904526961670815522767096127450386003813203809365323894442795443565820952283705939380656438309180252554808691019535681908983623214664516034111470695703020642485875959651583213619466594932918476670651633816994599772548478768526764012575954414322984173288627
a(168) <= 6941543021392713730431668387068999032987505813628626223678951265009922979171494889619620919629218172938050022712650390231108995307237169269667644098333312684776469399924110119789527532161256933656112818109620945798457804143586629828296071826627003328849527952336389650813108369731049080747183836913592892951933560765345204468790419691959105305515726737868378312872715843312320064073674571001295106119373097331445689095722655847864191050899780290639922180983329597857624757187701943317347314318342630851888782724340309365489828447876503970224596096163190175586664838655752084811432643865453475409306234610422754846201955355349982116992680801631254169733179214516679698471486732095757632702985749004267668618407596194879010235811205069773345370151540294560707067912911972617117872568917574563797510424723636252899372760040898527772334935423922327351299656281932266256675132502702322760435460536571309302586539469310861406622510368133332971804029286468542260235396204271045794929827474636467550655521103657096119618759746982193439030809406498947869770588717242290031299573971411197982166717351757954266001066384132372994264058429334563291496657469558139808375030168417007373133166391119553220773091860698215980720042621281779381114805103592526045494482900527480395872621990534353634675251867
a(256) <= 106345207806296484231668043910066785399795652556314098984703724996175611913155370425059004666755351126370765757325069220154090475525113111331534155822504132427954121926028977897326016452032633264303162177531381326310998970713694521304856783427108211035837719173191888424497687716945903847840832601158220338315116311569353516661115745397618364437941836386218808101529448483687495168944238726821330736995943973596941803495501200742109710969089802656966120128959989924056907838239415947883597253487288911265130861076995785143322559232949628580082040985968381890859811544811963250166807225739883175758540592938038640525057077635260377283817570121188506720763322577723854603213904763949026451035886610117960695498777558294914095190286423434103595325322044355050505888390419892966130432853384420025991603809604285550077998959033403957562518661694503445321270371924756278334786001733438835926798599715925477942244937628383988529536076933049398733022131632892984494328799535905089231306547424707999668050846457897292105617153237859066140231207977706483096753560267776977308513770417672719215980272226316038096369457350381579229798547106736019854318870385754141371733858517502044218801634760265587498814280073328060552232702804872921969797735332629722017664747892121030708748712733180842486503682755515481434761547891191431690407378061063299887695616928512486921716155822944378708863947668462062195571745339003058779915940858554595239390172360173769656161537253021381577803596097455028941144286297184282046724577533468348343936096263977229393852616124982192888432604948830175933041671162863393593616389115022094081675889914163162852300506873558662214056728175728839204797446701664449699367321558065141345504373533192399722226922311408612622529245371708935701643178960931071329253928802738471610262504489056899252740549408250528391001108587552456472577625704595893048563596869581967781113019047808212452621728173827862405874506295664794063113108306419852891590636875366731732762664553725634243782507523770949879136684328870372364698244368287699980886402179469945231457642085062803806579094674257318340352731256782194724089323