experimental-projects/pseudoprimes/generators/psp_from_psp.pl

#!/usr/bin/perl

# Generate pseudoprime from pseudoprimes, by replacing a few primes with other primes.

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

#my @nums = (51962615262396907, 330468624532072027, 2255490055253468347, 18436227497407654507);
#my @nums = ("3470207934739664512679701940114447720865");
#my @nums = (9857524690572481, 33439671284716801, 96653613831890401, 270136961300544031, 528096456788419441, 650643395658753601, 710238404427321601, 1822922951416158241, 4011563714063821201, 4525693104167627041, 4631812281009523441, 7049793086137296001, 8605736094003523201, 10449416165574628801, 11175581620177915681, 12746447178170148001, 12769123623410580481, 17705945296667070001);
#my @nums = (561, 62745, 576480525985, 1886616373665, 3193231538989185, 11947816523586945, 101817952350880305, 171800042106877185);
#my @nums = ("3470207934739664512679701940114447720865");
#my @nums = (341, 561, 645, 18705, 2113665, 2882265, 81722145, 9234602385, 19154790699045, 43913624518905, 56123513337585, 162522591775545, 221776809518265, 3274782926266545, 4788772759754985);
#my @nums = qw(7056721 79397009999 443372888629441 582920080863121 2491924062668039 14522256850701599 39671149333495681 242208715337316001 729921147126771599 842526563598720001 1881405190466524799 2380296518909971201 3188618003602886401 33711266676317630401 54764632857801026161 55470688965343048319 72631455338727028799);
#my @nums = (443372888629441, 39671149333495681, 842526563598720001, 2380296518909971201, 3188618003602886401);
#my @nums = (46657, 2433601, 67371265, 351596817937, 422240040001, 18677955240001, 458631349862401, 286245437364810001);
#my @nums = (1729, 46657, 2433601, 2628073, 19683001, 67371265, 110592000001, 351596817937, 422240040001, 432081216001, 2116874304001, 3176523000001, 18677955240001, 458631349862401, 286245437364810001, 312328165704192001);
#my @nums =  qw(443372888629441 582920080863121 39671149333495681 842526563598720001 2380296518909971201 3188618003602886401 33711266676317630401 54764632857801026161);
#my @nums = (561, 1105, 10585, 101101, 1024651, 10024561, 100427041, 1001152801, 10017089857, 100023777217, 1000151515441, 10000879761601, 100000782192961, 1000040508690301, 10000092861302401, 100001371359120001, 1000004296444433281, 10000011591390633121);
#my @nums = (561, 8911, 75361, 997633, 9890881, 99861985, 993905641, 9999109081, 99976607641, 999629786233, 9999501351841, 99994742993377, 999922265173441, 9999924433632001, 99999201310035841, 999996386511276505, 9999998594193164041);
#my @nums = (5310721, 2278677961, 9593125081, 29859667201, 467593730289953281);
#my @nums = qw(561 41041 825265 321197185 5394826801 232250619601 9746347772161 1436697831295441 60977817398996785 7156857700403137441 1791562810662585767521 87674969936234821377601 6553130926752006031481761 1590231231043178376951698401);
#my @nums = qw(35237869211718889547310642241 32809426840359564991177172754241 2810864562635368426005268142616001 349407515342287435050603204719587201 125861887849639969847638681038680787361 12758106140074522771498516740500829830401 2333379336546216408131111533710540349903201 294571791067375389885907239089503408618560001 130912961974316767723865201454187955056178415601 13513093081489380840188651246675032067011140079201 7482895937713262392883306949172917048928068129206401 1320340354477450170682291329830138947225695029536281601 379382381447399527322618466130154668512652910714224209601 70416887142533176417390411931483993124120785701395296424001 2884167509593581480205474627684686008624483147814647841436801 4754868377601046732119933839981363081972014948522510826417784001 1334733877147062382486934807105197899496002201113849920496510541601 260849323075371835669784094383812120359260783810157225730623388382401 112505380450296606970338459629988782604252033209350010888227147338120001);
#my @nums = qw(4788772759754985 38353281032877674865 2638294879881771254145 24773130788808935997465 429388072625313108651345 633708839387221385771985 4426632427184293146004185 30289748358904212366572385 728017010426459878356936705 34742187522900518220477982065 296874628838164374175009735905 282385466973939051351462060010785 303874597856107607075523212740305 95232935093163427870007414104051665 3470207934739664512679701940114447720865);
#my @nums = split(/\s*,\s*/, "68435117188079800987, 164853581396047908970027, 522925572082528736632187, 1820034970687975620484907, 4263739170243679206753787, 4360728281510798266333387, 28541906071781213329174507, 33833150661360980271172507, 84444874320158644422192427, 175352076630428496579381067, 270136290676063386556053067, 615437738523352001584590187, 3408560627000081376639770587, 11260257876970792445537580187");
my @nums = (51962615262396907, 330468624532072027, 2255490055253468347, 18436227497407654507);
#my @nums = qw(1729 46657 2628073 19683001 110592000001 432081216001 2116874304001 3176523000001 312328165704192001 12062716067698821000001 211215936967181638848001 411354705193473163968001 14295706553536348081491001 32490089562753934948660824001 782293837499544845175052968001 611009032634107957276386802479001);
#my @nums = (110592000001, 351596817937, 422240040001, 432081216001, 2116874304001, 3176523000001, 18677955240001, 458631349862401, 286245437364810001, 312328165704192001);
#my @nums = qw(399 8855 588455 139501439 3512071871 199195047359 14563696180319 989565001538399 20576473996736735 4049149795181043839 409810997884396741919 46852073639840281125599 6414735508880546179805759 466807799396932243821123839);
#my @nums = qw(58809496031 161513282399 244627234865 254080512449 276741041345 397745596079 482690075759 697522043735 846823631345 1468977455231 1681537931711 1800849630689 18682574710337 78999304047839 94175783290799);
#my @nums = qw(97739951021999 97822724866559 97894497697919 98176250489471 98370671617295 98557811825759 98631388831535 98675974630079 98877965805359 98898869754719 98987029858079 99038395076543 99087791115599 99156166237799 99218389998959 99223733571479 99269920007999 99355592649599 100549434718655 100633672707359 100774697490719 101239730807039 101323992409199 101477206831679 101494262610719 101705678526815 101776183991999 101793709675679 101810036746439 101928905114399 102005239549499 102190288717439 102407410531439 102409922275199 102416785408223 102665801468879 102762629942399 102855039087359 103120427377799 103355182641599 103597485213599 103726812293495);

my %seen;
my $limit = 1e4;

sub is_lucas_carmichael ($n) {

    if ($n > ~0 ){
        $n = Math::GMPz->new($n);
    }

    my $t = $n + 1;
    vecall { $t % ($_ + 1) == 0 } Math::Prime::Util::GMP::factor($n);
}

foreach my $n (@nums) {
#while (<>) {
#    my ($n) = (split(' ', $_))[-1];

    $n || next;

    my @terms;
    forsquarefree {
        if (gcd($n, $_) == 1) {
            push @terms, $_;
        }
    } $limit;

    my @f = Math::Prime::Util::GMP::factor($n);

    foreach my $k (1 .. 2) {

        last if (scalar(@f) - 1 <= $k);

        forcomb {
            my $factor = Math::Prime::Util::GMP::vecprod(@f[@_]);

            for (@terms) {
                my $t = Math::Prime::Util::GMP::mulint($factor, $_);

                if ($t > 1e15 and Math::Prime::Util::GMP::is_pseudoprime($t, 2) and $t ne $n) {
                #if ($t > 1e12 and is_lucas_carmichael($t) and $t ne $n) {
                    say $t if !$seen{$t}++;
                }
            }
        } scalar(@f), scalar(@f) - $k;
    }
}