gauss-euler_counterexample.pl

#!/usr/bin/perl

# Try to find a counter-example to the following 26+4 test:
#   https://arxiv.org/pdf/2311.07048.pdf

# See also:
#   https://www.mersenneforum.org/showthread.php?t=27288&page=3

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

sub is_ok($n, $z) {

    Math::Prime::Util::GMP::is_strong_pseudoprime($n, $z) || return;
    Math::GMPz::Rmpz_sub_ui($z, $z, 2);
    Math::Prime::Util::GMP::is_strong_pseudoprime($n, $z) || return;
    Math::GMPz::Rmpz_add_ui($z, $z, 1);
    Math::Prime::Util::GMP::is_strong_pseudoprime($n, $z) || return;
    Math::GMPz::Rmpz_add_ui($z, $z, 2);
    Math::Prime::Util::GMP::is_strong_pseudoprime($n, $z) || return;
    Math::GMPz::Rmpz_add_ui($z, $z, 1);
    Math::Prime::Util::GMP::is_strong_pseudoprime($n, $z) || return;

    return 1;
}

my $z = Math::GMPz::Rmpz_init();

while (<>) {

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

    $n || next;

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

    Math::GMPz::Rmpz_set_str($z, "$n", 10);
    Math::GMPz::Rmpz_sqrt($z, $z);
    is_ok($n, $z) || next;

    say "Strong candidate: $n";

    my $ok = 1;
    foreach my $k (2, 3, 5, 7) {
        Math::GMPz::Rmpz_set_str($z, "$n", 10);
        Math::GMPz::Rmpz_div_ui($z, $z, $k);
        Math::GMPz::Rmpz_sqrt($z, $z);
        if (not is_ok($n, $z)) {
            $ok = 0;
            last;
        }
    }

    if ($ok) {
        die "Counter-example: $n";
    }
}

__END__
Strong candidate: 33577362035427547
Strong candidate: 66799233831435661
Strong candidate: 2126730403061568481
Strong candidate: 801475619827501
Strong candidate: 17382942756591571116689204567251
Strong candidate: 421388268445534102651
Strong candidate: 2087523327838745971351
Strong candidate: 35491807953253
Strong candidate: 98482998659653
Strong candidate: 247304741216653
Strong candidate: 936029516476753
Strong candidate: 202278967333409551940317
Strong candidate: 2547824360659482079150411
Strong candidate: 2736700706799799817698981
Strong candidate: 17549634678726794947542331
Strong candidate: 19619535851111080779494491
Strong candidate: 4736959538130074753976271501
Strong candidate: 21298066960797290008315675981
Strong candidate: 1396956675261421
Strong candidate: 1748929333788253
Strong candidate: 1818269413374781
Strong candidate: 1820763947860201
Strong candidate: 4180459179686653
Strong candidate: 1240231697100669301580000053153
Strong candidate: 331283599542836714881
Strong candidate: 1196372393510837715901
Strong candidate: 115244331850772213443201
Strong candidate: 4988827923413437
Strong candidate: 435136583547090937
Strong candidate: 1676991107224649318761789260301
Strong candidate: 75257154388706023071521
Strong candidate: 188464763337512904668161
Strong candidate: 4619825290614895285579776001
Strong candidate: 366561981379415638100780135641
Strong candidate: 414775787512777289605001428392961
Strong candidate: 27393967090456157700880458957419898348001
Strong candidate: 9278429690310147005187985717030752794327663339521
Strong candidate: 29459595391587275041
Strong candidate: 197734612396517932861
Strong candidate: 5831377063293410935741
Strong candidate: 12307392018216273778381
Strong candidate: 55134316712426407837214653
Strong candidate: 21799679499855951440790695653
Strong candidate: 47358126264277687729736538260640361
Strong candidate: 4808909621762460059206771635409661401
Strong candidate: 53746997020689787957114446770698223988181