123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110 |
- #!/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
|