trizen
/
experimental-projects


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
							#!/usr/bin/perl

# Author: Daniel "Trizen" Șuteu
# Date: 28 January 2019
# https://github.com/trizen

# A new algorithm for generating Fermat pseudoprimes to base 2.

# See also:
#   https://oeis.org/A050217 -- Super-Poulet numbers: Poulet numbers whose divisors d all satisfy d|2^d-2.
#   https://oeis.org/A214305 -- Fermat pseudoprimes to base 2 with two prime factors.

# See also:
#   https://en.wikipedia.org/wiki/Fermat_pseudoprime
#   https://trizenx.blogspot.com/2018/08/investigating-fibonacci-numbers-modulo-m.html

use 5.020;
use warnings;
use experimental qw(signatures);

# a(8) <= 1381755790801
# a(8) <= 139309114031

# a(9) <= 29982298886401
# a(9) <= 7947339136801

# a(10) <= 72054898434289

use Math::AnyNum qw(prod);
#~ use ntheory qw(forcomb forprimes kronecker divisors lucas_sequence powmod);

use strict;
use ntheory qw(:all);

my @A000229 = (3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 422231, 701399, 366791, 3818929, 9257329, 22000801, 36415991, 48473881, 175244281, 120293879);

my $N = 7;

# a(5) = 11530801
# a(7) = 15656266201

my @primes = @{primes(100)};

sub non_residue {
    my ($n, $q) = @_;

    foreach my $p (@primes) {

        if ($p > $q) {
            return -1;
        }

        sqrtmod($p, $n) // return $p;
    }

    return -1;
}

#~ #139309114031, a(9) <= 7947339136801, a(10) <= 72054898434289.
#~ say non_residue(139309114031, nth_prime(8));
#~ say non_residue(7947339136801, nth_prime(9));
#~ say non_residue(72054898434289, nth_prime(10));

#~ __END__
#~ say non_residue(72054898434289, nth_prime(10));

#~ __END__

sub isok {
    my ($n, $k) = @_;

    my $p = nth_prime($n);

    if (powmod($p, ($k-1)>>1, $k) == $k-1)  {
        my $q = non_residue($k, $p);

        if ($p == $q) {
            return 1;
        }

        return;
    }

    return;

    #~ my $res;
    #~ my $p = nth_prime($n);

    #~ for(my $k = $A000229[$n-1]*$A000229[$n-1]; ; $k+=2) {

        #~ if (!is_prime($k) and powmod($p, ($k-1)>>1, $k) == $k-1) {
            #~ my $q = non_residue($k, $p);

            #~ if ($p == $q) {
                #~ return $k;
            #~ }
        #~ }
    #~ }

    #~ return $res;
}

sub fermat_pseudoprimes ($limit, $callback) {

    my %common_divisors;

    my $P = nth_prime($N);

    forprimes {
        my $p = $_;
        foreach my $d (divisors($p - 1)) {
            if (powmod($P, $d, $p) == $p-1) {
                push @{$common_divisors{$d}}, $p;
            }
        }
    } $limit;

    my %seen;

    foreach my $arr (values %common_divisors) {

        my $l = $#{$arr} + 1;

        foreach my $k (2) {
            forcomb {
                my $n = prod(@{$arr}[@_]);
                #if ($n <= 72054898434289) {
                    $callback->($n) if !$seen{$n}++;
               # }
            } $l, $k;
        }
    }
}

#~ sub is_fermat_pseudoprime ($n, $base) {
    #~ powmod($base, $n - 1, $n) == 1;
#~ }

#~ sub is_fibonacci_pseudoprime($n) {
    #~ (lucas_sequence($n, 1, -1, $n - kronecker($n, 5)))[0] == 0;
#~ }

my @values;

fermat_pseudoprimes(
    5_000_000,
    sub ($k) {

      #  is_fermat_pseudoprime($n, 2) || die "error for n=$n";

        #~ if (kronecker($n, 5) == -1) {
            #~ if (is_fibonacci_pseudoprime($n)) {
                #~ die "Found a special pseudoprime: $n = prod(@f)";
            #~ }
        #~ }


    if (isok($N, $k)) {
        say $k;
        push @values, $k;
    }

       # push @pseudoprimes, $n;
    }
);


say "Min: a($N) <= ", vecmin(@values);

#@pseudoprimes = sort { $a <=> $b } @pseudoprimes;

#say join(', ', @pseudoprimes);

__END__
341, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321, 10261, 13747, 14491, 15709, 18721, 19951, 23377, 31417, 31609, 31621, 35333, 42799, 49141, 49981, 60701, 60787, 65077, 65281, 80581, 83333, 85489, 88357, 90751, 104653, 123251, 129889, 130561, 150851, 162193, 164737, 181901, 188057, 194221, 196093, 215749, 219781, 220729, 226801, 233017, 241001, 249841, 253241, 256999, 264773, 271951, 275887, 280601, 282133, 294271, 294409, 318361, 357761, 390937, 396271, 422659, 435671, 443719, 452051, 458989, 481573, 486737, 489997, 513629, 514447, 556169, 580337, 582289, 587861, 604117, 611701, 642001, 647089, 653333, 657901, 665281, 665333, 672487, 679729, 680627, 688213, 710533, 721801, 722201, 722261, 729061, 741751, 742813, 745889, 769567, 769757, 818201, 838861, 873181, 877099, 916327, 976873, 983401, 1016801, 1053761, 1064053, 1073021, 1082401, 1092547, 1109461, 1132657, 1145257, 1168513, 1207361, 1251949, 1252697, 1277179, 1293337, 1302451, 1325843, 1357441, 1373653, 1398101, 1433407, 1441091, 1457773, 1493857, 1507963, 1509709, 1530787, 1537381, 1549411, 1584133, 1678541, 1690501, 1730977, 1735841, 1755001, 1809697, 1811573, 1826203, 1840357, 1876393, 1969417, 1987021, 1994689, 2004403, 2008597, 2035153, 2081713, 2134277, 2163001, 2181961, 2184571, 2205967, 2261953, 2264369, 2269093, 2284453, 2304167, 2313697, 2387797, 2434651, 2487941, 2491637, 2510569, 2617451, 2649029, 2670361, 2746477, 2746589, 2748023, 2757241, 2811271, 2909197, 2944261, 2976487, 2977217, 3059101, 3090091, 3116107, 3125281, 3235699, 3337849, 3345773, 3363121, 3375041, 3375487, 3400013, 3413533, 3471071, 3539101, 3542533, 3567481, 3568661, 3656449, 3898129, 3911197, 3985921, 4082653, 4097791, 4101637, 4151869, 4181921, 4188889, 4314967, 4360621, 4361389, 4415251, 4469471, 4480477, 4513841, 4567837, 4863127, 4868701, 4869313, 4922413, 5016191, 5044033, 5095177, 5131589, 5173169, 5173601, 5176153, 5256091, 5351537, 5423713, 5489641, 5524693, 5575501, 5590621, 5672041, 5766001, 5919187, 6027193, 6122551, 6140161, 6226193, 6233977, 6236257, 6278533, 6334351, 6368689, 6386993, 6539527, 6631549, 6658669, 6749021, 6779137, 6787327, 6912079, 6952037, 6955541, 6973063, 7017193, 7232321, 7295851, 7306261, 7306561, 7462001, 7674967, 7725901, 7759937, 7820201, 7883731, 8036033, 8095447, 8180461, 8231653, 8239477, 8362201, 8534233, 8650951, 8725753, 8745277, 8902741, 9006401, 9037729, 9040013, 9056501, 9073513, 9131401, 9273547, 9371251, 9480461, 9533701, 9564169, 9567673, 9591661, 9724177, 9729301, 9863461, 10031653, 10084177, 10331141, 10386241, 10402237, 10403641, 10425511, 10505701, 10610063, 10712857, 10974881, 11115037, 11335501, 11367137, 11541307, 11585293, 12032021, 12263131, 12273769, 12322133, 12498061, 12599233, 12659989, 12711007, 12854437, 13073941, 13295281, 13338371, 13421773, 13448593, 13635289, 13694761, 13747361, 13773061, 13856417, 13991647, 13996951, 14026897, 14179537, 14282143, 14324473, 14589901, 14794081, 14899751, 15101893, 15139199, 15162941, 15188557, 15268501, 15525241, 15583153, 15621409, 15732721, 15757741, 15802681, 15976747, 15978007, 16070429, 16324001, 16349477, 16435747, 16705021, 16717061, 16818877, 16853077, 16879501, 16973393, 17116837, 17134043, 17208601, 17327773, 17375249, 17405537, 17590957, 17759681, 17777191, 17870561, 18067501, 18073817, 18366937, 18443701, 18535177, 18653353, 18736381, 18740971, 18985627, 19020191, 19328653, 19404139, 19985269, 20081953, 20117467, 20234341, 20261251, 20647621, 20770621, 21303343, 21306157, 21355951, 21397381, 21400481, 21623659, 21654533, 21907009, 22137809, 22369621, 22591301, 22669501, 22953673, 23247901, 23261713, 23315977, 23464033, 23577497, 23734901, 23822329, 23828017, 23963869, 24904153, 25276421, 25326001, 25457833, 25696133, 25768261, 25909453, 26377921, 26470501, 26886817, 26977001, 27108397, 27219697, 27331921, 27380831, 27392041, 27409541, 27491237, 27492581, 27509653, 27664033, 27798461, 27808463, 28011001, 28325881, 28406953, 28527049, 28572961, 28717483, 29143633, 29581501, 29593159, 30058381, 30185569, 30219757, 30295141, 30529693, 30881551, 31040833, 31150351, 31166803, 31436123, 31735621, 31759121, 31766983, 32091781, 32095057, 32168117, 32676481, 32701297, 33600533, 33627301, 33704101, 33840397, 34003061, 34100821, 34856167, 34890481, 35498467, 35820937, 35851037, 36255451, 36307981, 36448387, 36721021, 36724591, 36919681, 36974341, 36981601, 37109467, 37439201, 37469701, 37962541, 38010307, 38118763, 38210323, 38439523, 38903287, 38971661, 39052333, 40325041, 40361197, 40629601, 41662297, 41840809, 42344609, 42485119, 42623017, 42702661, 42709591, 42984589, 43363601, 43661257, 43798457, 44482901, 44671001, 45175201, 45219329, 45879941, 46094401, 46256489, 46325029, 46469809, 46517857, 46657181, 47253781, 47903701, 47918581, 48064021, 48191653, 48316969, 48448661, 48563089, 49075417, 50376019, 50523661, 51283501, 51627817, 52119289, 52181407, 52204237, 53154337, 53283169, 53542147, 53675623, 54449431, 55318957, 55610837, 55729957, 56420033, 56810137, 58422409, 58449847, 58679941, 59999011, 60352921, 60696661, 60738257, 61201009, 61377109, 61754941, 61832377, 62289541, 63001801, 63167743, 63318169, 63388033, 63781901, 64605041, 64735897, 65144501, 65254393, 65565457, 66096253, 66384121, 66790057, 66932851, 67194401, 67763803, 68102641, 68512867, 68621701, 68839597, 69176647, 69228967, 69485281, 69705529, 69885649, 69917371, 70541099, 70626301, 72543547, 72595951, 72884701, 74411131, 74658629, 74927161, 75140137, 75143251, 75565873, 77295961, 77594653, 78526729, 78795181, 79398901, 79464533, 80142761, 80375707, 80918281, 81954133, 82452061, 82870517, 82882753, 84164033, 85207669, 85400701, 85759147, 86438857, 86999837, 87558127, 88930463, 89244901, 89308771, 89784581, 90014653, 90341197, 90803429, 91433281, 92645437, 93431521, 93591721, 93926197, 94502701, 95451361, 96618397, 96888641, 96904081, 96916279, 97655933, 98523877, 99898801, 99945007, 100463443, 100860997, 100943201, 101152133, 101218921, 101270251, 101276579, 102690901, 103022551, 103301633, 104078857, 104524421, 106485121, 108596953, 109322501, 109541461, 110139499, 110413333, 111654401, 112828801, 113605201, 114305441, 114329881, 116090081, 116151661, 117987841, 119558011, 121128361, 121374241, 123671671, 125686241, 126886447, 127710563, 128027831, 128536561, 129205781, 129461617, 130944133, 133427449, 133467517, 134767153, 135945853, 135969401, 138336661, 138736153, 140710421, 143168581, 145206361, 148910653, 150260893, 150988753, 151533377, 153369061, 155840777, 157010389, 158397247, 158496911, 158895281, 159874021, 161498681, 163442551, 163759753, 165938653, 166082309, 166444181, 167692141, 168566501, 170782921, 172116181, 176597821, 177951973, 183554407, 186846301, 187667969, 188985961, 193330237, 196049701, 206028271, 206453509, 214858717, 217472501, 220261861, 221415781, 224957893, 227518271, 231927781, 235742513, 242239321, 242729401, 242860069, 246099317, 246282511, 247321301, 249993101, 251663837, 258234401, 260963389, 262979501, 271682651, 277897813, 282769771, 283936001, 287449091, 351593899, 367632301, 434042801, 457457617, 464955857, 491738801, 516045197, 536870911, 604611019, 611097401, 612006253, 630622753, 762278161, 1101673501, 1220114377, 1299963601, 1319978701, 1441139641, 1473580001, 1541955409, 1767200059, 1831258601, 1879623157, 1921295359, 2284569169, 2299876417, 2344578077, 2454285751, 2813372869, 2882370481, 2930420351, 3002647829, 3034402681, 3045287797, 3271999249, 3277047649, 3323308501, 3516565057, 3576818293, 3650158849, 4215885697, 4295435629, 4384806451, 4550912389, 4562359201, 4563568819, 5099822341, 5256967999, 5726579371, 5847309901, 6082391617, 6221531233, 6950197069, 6958248277, 7030714813, 7112441977, 7315201219, 7477382953, 7492766161, 7629221377, 8025562777, 8173975021, 8352286141, 8768530501, 8788016089, 9536234593, 9752463781, 9761467669, 9821404321, 9972894583, 10545166433, 11500521553, 11847382193, 12236182687, 12640344193, 13028197207, 13079177569, 13143202489, 13802550829, 15972404197, 16365760993, 17112890881, 17261652461, 17522471101, 18229099393, 18723407341, 19089110641, 19463358097, 19613665009, 19742849041, 20378724731, 21468635801, 21604034453, 21792816121, 22286956957, 23652189937, 24177482089, 25023836701, 25258781377, 28068637801, 28741893457, 30219719053, 30606632449, 31221259651, 31675383749, 32456510101, 32682958897, 34872201649, 35084290453, 36501164509, 37408911097, 37418488801, 38256564721, 39816655441, 39974135479, 42099340541, 42352289149, 43215089153, 45983665729, 49944700297, 50032571509, 50294058751, 51094460611, 52301578177, 52474339009, 54106327309, 57097913533, 59850086533, 60627562673, 63776528677, 65700513721, 67965754429, 68076644569, 69674020529, 70961435533, 78889735961, 91918256041, 97951750513, 99737787437, 100004790097, 102125919421, 103816620793, 104562831313, 105207688757, 106276453183, 114713483491, 115920835801, 119539191313, 120751007161, 125402926477, 147071092213, 147523256371, 149583518641, 152230013833, 155573122993, 157727525581, 162285344173, 168003672409, 176529862601, 191557957189, 193601185171, 194305088689, 204364047301, 207406632007, 215580073453, 227959335001, 229352039821, 236028946357, 254972682157, 256737574117, 257506553303, 273178641961, 276676965109, 300386596273, 315429282901, 321147704461, 323743143781, 324469827349, 381491063773, 386091460621, 393357094201, 394679330431, 407170183999, 428178002569, 442429869787, 457804259249, 540735505421, 544848826103, 575176785409, 582561482161, 589837675213, 615498368941, 662105774101, 753465725557, 789187877941, 823505345737, 885621580601, 918660756421, 942860724457, 966644066221, 1004503769443, 1009461720193, 1042789205881, 1100586419201, 1124192318441, 1179704173789, 1261099046791, 1337522173969, 1537515050737, 1544001719761, 1686227913481, 2295556566571, 4117335954337, 6609805108033, 7011894390607, 10531005131701, 10918700104589, 11014157148289, 12268183891489, 12272059592053, 13647788986217, 14574316854529, 16024031668279, 16376643470449, 20899529882683, 21362883096721, 23151106436839, 23353046634997, 24733621097461, 33009739922881, 40925790926473, 47760948758851, 48891529247017, 62262075657697, 63673836026149, 65921528095249, 82903970990413, 85612464077149, 86127405910417, 104283827002213, 111730064562049, 135617992212961, 163387540639621, 322053315634073, 444472412391001, 522071952204541, 780471380082577, 1264022137981459, 1930742640637021, 2152651577916349, 2528106044429827, 4919377722161653, 6558405110693347, 22215554968098913, 45780658476273103, 63557753308812569, 136453030604037307, 319212794453773993, 14054662152215842621