solovay_strassen_pseudoprimes.pl

#!/usr/bin/perl

# a(n) is the least number for which the Solovay-Strassen primality test on bases < p fails.
# https://oeis.org/A007324

use 5.020;
use strict;
use warnings;

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

sub count_fails ($k) {

    my $count = 0;
    my $base  = 2;
    my $exp   = ($k - 1) >> 1;

    while (powmod($base, $exp, $k) == (kronecker($base, $k) % $k)) {
        ++$count;
        ++$base;
    }

    return $count;
}

my %table;

while (<>) {
    next if /^\h*#/;
    /\S/ or next;
    my $n = (split(' ', $_))[-1];

    $n || next;

    next if length($n) > 50;
    Math::Prime::Util::GMP::is_pseudoprime($n, 2) || next;

    if ($n > ((~0) >> 2)) {
        $n = Math::GMPz::Rmpz_init_set_str($n, 10);
    }

    my $count = prime_count(count_fails($n)) || next;

    if (not exists $table{$count}) {
        $table{$count} = $n;
        say "a($count) <= $n";
    }
    elsif ($n < $table{$count}) {
        $table{$count} = $n;
        say "a($count) <= $n";
    }
}

say "\n=>> Final results:\n";

foreach my $k (sort { $a <=> $b } keys %table) {
    say "a($k) <= $table{$k}";
}

__END__
a(1)  = 561
a(2)  = 1729
a(3)  = 1729
a(4)  = 399001
a(5)  = 399001
a(6)  = 1857241
a(7)  = 1857241
a(8)  = 6189121
a(9)  = 14469841
a(10) = 14469841
a(11) = 14469841
a(12) = 86566959361
a(13) = 311963097601
a(14) = 369838909441
a(15) = 6389476833601
a(16) = 6389476833601

a(17) <= 1606205228509922041
a(18) <= 1606205228509922041
a(19) <= 1606205228509922041
a(20) <= 1606205228509922041

# Other upper-bounds:

a(2) <= 10585
a(3) <= 1729
a(4) <= 488881
a(5) <= 399001
a(6) <= 2433601
a(7) <= 1857241
a(8) <= 6189121
a(9) <= 549538081
a(10) <= 50201089
a(11) <= 14469841
a(12) <= 86566959361
a(13) <= 311963097601
a(14) <= 369838909441
a(15) <= 31929487861441
a(16) <= 6389476833601
a(17) <= 106330673133121873921
a(18) <= 1092544711125977802501649
a(19) <= 7389375890056398001
a(20) <= 1606205228509922041
a(21) <= 166480672916471266912828590721
a(22) <= 299774827640366612231286196609
a(27) <= 51869154461968006838855041
a(46) <= 105216055594390884840438324972769319399722594046651360392070071794973423530188471087867855419188813164954561140227145977855514336985746250989366318940490798583710597151720075427387437940535767395296272532149397065590267303873620351321073058502920032770522836726669005262088263964215455869031740912313201227043
a(62) <= 2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867
a(100) <= 4755444900898962640570805079622407945513196432011911985648410022240088808985889200376095787527901239245756068158548164080646419498193938363223751878040975178651652955930683319090515589565114950046340315137578332784425652394857192999191244130079906060771897042318182261565231930157836276911534989784532752912947610193310744025493450293981924804993015182502555790249587996752315485361179895260300891395439822476185769523434215286135938029039660904526961670815522767096127450386003813203809365323894442795443565820952283705939380656438309180252554808691019535681908983623214664516034111470695703020642485875959651583213619466594932918476670651633816994599772548478768526764012575954414322984173288627
a(168) <= 6941543021392713730431668387068999032987505813628626223678951265009922979171494889619620919629218172938050022712650390231108995307237169269667644098333312684776469399924110119789527532161256933656112818109620945798457804143586629828296071826627003328849527952336389650813108369731049080747183836913592892951933560765345204468790419691959105305515726737868378312872715843312320064073674571001295106119373097331445689095722655847864191050899780290639922180983329597857624757187701943317347314318342630851888782724340309365489828447876503970224596096163190175586664838655752084811432643865453475409306234610422754846201955355349982116992680801631254169733179214516679698471486732095757632702985749004267668618407596194879010235811205069773345370151540294560707067912911972617117872568917574563797510424723636252899372760040898527772334935423922327351299656281932266256675132502702322760435460536571309302586539469310861406622510368133332971804029286468542260235396204271045794929827474636467550655521103657096119618759746982193439030809406498947869770588717242290031299573971411197982166717351757954266001066384132372994264058429334563291496657469558139808375030168417007373133166391119553220773091860698215980720042621281779381114805103592526045494482900527480395872621990534353634675251867
a(256) <= 106345207806296484231668043910066785399795652556314098984703724996175611913155370425059004666755351126370765757325069220154090475525113111331534155822504132427954121926028977897326016452032633264303162177531381326310998970713694521304856783427108211035837719173191888424497687716945903847840832601158220338315116311569353516661115745397618364437941836386218808101529448483687495168944238726821330736995943973596941803495501200742109710969089802656966120128959989924056907838239415947883597253487288911265130861076995785143322559232949628580082040985968381890859811544811963250166807225739883175758540592938038640525057077635260377283817570121188506720763322577723854603213904763949026451035886610117960695498777558294914095190286423434103595325322044355050505888390419892966130432853384420025991603809604285550077998959033403957562518661694503445321270371924756278334786001733438835926798599715925477942244937628383988529536076933049398733022131632892984494328799535905089231306547424707999668050846457897292105617153237859066140231207977706483096753560267776977308513770417672719215980272226316038096369457350381579229798547106736019854318870385754141371733858517502044218801634760265587498814280073328060552232702804872921969797735332629722017664747892121030708748712733180842486503682755515481434761547891191431690407378061063299887695616928512486921716155822944378708863947668462062195571745339003058779915940858554595239390172360173769656161537253021381577803596097455028941144286297184282046724577533468348343936096263977229393852616124982192888432604948830175933041671162863393593616389115022094081675889914163162852300506873558662214056728175728839204797446701664449699367321558065141345504373533192399722226922311408612622529245371708935701643178960931071329253928802738471610262504489056899252740549408250528391001108587552456472577625704595893048563596869581967781113019047808212452621728173827862405874506295664794063113108306419852891590636875366731732762664553725634243782507523770949879136684328870372364698244368287699980886402179469945231457642085062803806579094674257318340352731256782194724089323