swap_factors.pl

#!/usr/bin/perl

use 5.014;

use Math::GMPz;
use List::Util qw(uniq);
use ntheory qw(forsemiprimes forprimes factor forsquarefree random_prime  );
use Math::Prime::Util::GMP qw(mulint is_pseudoprime vecprod divint sqrtint divisors gcd);

# 3274782926266545
# 4788772759754985
# 633708839387221385771985
# 85866492509341408342261785
# 1153582279094600286115568385
# 38049785538164232203093987265
# 9239040473268653691499587195465
# 55428474928216449147566945330865
# 304740732375157335714579744005385

#~ 687704738507315339413174636065
#~ 4125799098581345329437336507465
#~ 35784743100970575065929487616705
#~ 93934885805169798001550107714545

#~ 4655734127045
#~ 221776809518265
#~ 3274782926266545
#~ 4788772759754985
#~ 38353281032877674865
#~ 2638294879881771254145
#~ 24773130788808935997465
#~ 429388072625313108651345
#~ 633708839387221385771985
#~ 13436161237966288348110585
#~ 8074730241975744403202730585
#~ 64670514507983736925250669255265

# 4426632427184293146004185
# 429388072625313108651345
# 266337095804598854461505143065
# 2133093800299032225382194690807585
# 76863331618321292940799905
# 4426632427184293146004185

#~ 221776809518265
#~ 3274782926266545
#~ 4788772759754985
#~ 44445311134962585
#~ 136836291472769505
#~ 331898284250350665
#~ 612756519790891785
#~ 1121391818823450945
#~ 1326249209093672865
#~ 1776210467431784385
#~ 2176485176509015065
#~ 2790959548188872985
#~ 3005741099401045545
#~ 3486467789908607505
#~ 5875480119318227265
#~ 6686415419518378545
#~ 6967562024635331505
#~ 10382924891216612505
#~ 10656153920543114985
#~ 10866946026210257985
#~ 12142602391592154945
#~ 12909374329071388785
#~ 13709382959660636865
#~ 17350265139042425745

# 251324857051150634717505, 4298985769199999538585, 58264154129967593746442505
# 46534068369757323368492865, 4298985769199999538585, 58264154129967593746442505
# 94431368119882647887265, 46534068369757323368492865, 4298985769199999538585

# 3486467789908607505, 6686415419518378545, 6967562024635331505, 4788772759754985
# 633708839387221385771985, 30449076023716600364958107265, 5075374094652256078647827865

# 3107353551594110575521369407046227985, 41771944171151419698571866577673865, 32135905844445616613674965617710785
# 3178327865071658746992945293797905, 6543514918337095245925022641540545, 58361005458182925354581213657907242505
# 6543514918337095245925022641540545, 58361005458182925354581213657907242505, 218924994654832550816515785
# 5551200871830513970028352466076188185, 30289748358904212366572385, 639279061696677004929094997372145

# 609299754103181490100455705
# 5551200871830513970028352466076188185, 30289748358904212366572385, 156693987228084145384168898338065
# 5821477606342877287368646390305, 1455392118896988500001436526865, 156693987228084145384168898338065
# 1370862939340854730059272985
# 2620169904670649052334519366844385
# 6752727999005617757947385377498566305370945, 1447019058278583487014876666838646972760705
# 2012729986647758693189432627820105025467340545
# 14089090063942564942304718922492104414299518785
# 156693987228084145384168898338065, 301153464627386708780887273262792222865, 7528989392322215101563931396245685185
# 639279061696677004929094997372145, 389070990460152895292891577255663796305, 3307098624318336884912041438460661977505
# 156693987228084145384168898338065, 301153464627386708780887273262792222865, 7528989392322215101563931396245685185

# 389070990460152895292891577255663796305, 3307098624318336884912041438460661977505, 14089090063942564942304718922492104414299518785, 2012729986647758693189432627820105025467340545, 1370862939340854730059272985
# 2620169904670649052334519366844385
# 14089090063942564942304718922492104414299518785, 2012729986647758693189432627820105025467340545
# 13619855197403642505743435147863830105, 156693987228084145384168898338065, 389070990460152895292891577255663796305

# 156693987228084145384168898338065
# 1455392118896988500001436526865
# 5821477606342877287368646390305
# 2632787600289811236737758837545

# 218924994654832550816515785
# 30289748358904212366572385
# 609299754103181490100455705

#~ 3107353551594110575521369407046227985
#~ 41771944171151419698571866577673865
#~ 32135905844445616613674965617710785
#~ 3178327865071658746992945293797905
#~ 6543514918337095245925022641540545
#~ 58361005458182925354581213657907242505
#~ 609299754103181490100455705
#~ 2620169904670649052334519366844385
#~ 218924994654832550816515785
#~ 5551200871830513970028352466076188185
#~ 2632787600289811236737758837545
#~ 30289748358904212366572385
#~ 5821477606342877287368646390305
#~ 1455392118896988500001436526865
#~ 13619855197403642505743435147863830105
#~ 156693987228084145384168898338065
#~ 301153464627386708780887273262792222865
#~ 7528989392322215101563931396245685185
#~ 6752727999005617757947385377498566305370945
#~ 1447019058278583487014876666838646972760705
#~ 639279061696677004929094997372145
#~ 389070990460152895292891577255663796305
#~ 3307098624318336884912041438460661977505
#~ 14089090063942564942304718922492104414299518785
#~ 2012729986647758693189432627820105025467340545
#~ 1370862939340854730059272985

# 39898386437874778336787265, 687704738507315339413174636065, 4125799098581345329437336507465
# 4125799098581345329437336507465, 687704738507315339413174636065, 39898386437874778336787265

#~ 1.9801 record: 3307098624318336884912041438460661977505
#~ 1.9731 record: 10092362094594076578926570519025778129785
#~ 1.9753 record: 12804114195310937542216014575625232525185
#~ 1.9731 record: 67190462911126877171884960163556426292185
#~ 1.9790 record: 1447019058278583487014876666838646972760705
#~ 1.9790 record: 6752727999005617757947385377498566305370945
#~ 1.9790 record: 14470122821881303970212852593003903516440385
#~ 1.9790 record: 17725898762781984091012346574545217652360305
#~ 1.9790 record: 18328820233319147076345586200756572121975105

# 136175808701462527139922181690151865
# 18322261399861557009937979582411606865
# 11188420062660109059016836239101375905

# 104218464815136937688132622425591846968504305, 5821477606342877287368646390305, 11188420062660109059016836239101375905, 14470122821881303970212852593003903516440385, 6752727999005617757947385377498566305370945, 1447019058278583487014876666838646972760705
# 11188420062660109059016836239101375905, 1455392118896988500001436526865, 2797148676542619034911260891148907665
# 136175808701462527139922181690151865, 5821477606342877287368646390305, 7528989392322215101563931396245685185
# 5821477606342877287368646390305, 11188420062660109059016836239101375905, 2797148676542619034911260891148907665
# 1842836800348739399588385, 5821477606342877287368646390305, 1455392118896988500001436526865

#~ 1.9810 record: 1370862939340854730059272985
#~ 1.9801 record: 14089090063942564942304718922492104414299518785
#~ 1.9801 record: 2012729986647758693189432627820105025467340545
#~ 1.9801 record: 3307098624318336884912041438460661977505
#~ 1.9797 record: 389070990460152895292891577255663796305
#~ 1.9797 record: 639279061696677004929094997372145
#~ 1.9790 record: 7528989392322215101563931396245685185
#~ 1.9790 record: 6752727999005617757947385377498566305370945
#~ 1.9790 record: 1447019058278583487014876666838646972760705
#~ 1.9790 record: 18328820233319147076345586200756572121975105
#~ 1.9790 record: 14470122821881303970212852593003903516440385
#~ 1.9790 record: 17725898762781984091012346574545217652360305

# 30289748358904212366572385, 13619855197403642505743435147863830105, 156693987228084145384168898338065, 389070990460152895292891577255663796305, 3307098624318336884912041438460661977505
# 5821477606342877287368646390305, 18328820233319147076345586200756572121975105, 6752727999005617757947385377498566305370945, 1447019058278583487014876666838646972760705

#~ 639279061696677004929094997372145
#~ 2632787600289811236737758837545
#~ 218924994654832550816515785
#~ 30289748358904212366572385
# 1132535995673545452074924146972665
# 13619855197403642505743435147863830105, 156693987228084145384168898338065, 389070990460152895292891577255663796305, 3307098624318336884912041438460661977505
# 609299754103181490100455705
# 3278282922943952669012673870465
# 2632787600289811236737758837545, 13619855197403642505743435147863830105, 156693987228084145384168898338065, 389070990460152895292891577255663796305, 14089090063942564942304718922492104414299518785, 2012729986647758693189432627820105025467340545

#~ 13619855197403642505743435147863830105
#~ 1132535995673545452074924146972665
#~ 156693987228084145384168898338065
#~ 2632787600289811236737758837545

#~ 4899856299584863138737230040441981737463534244985985
#~ 19599419160149492611672840593470043489539060577922305
#~ 93097233462972639976350893358610352249916692242603905
#~ 1177059715761219117658883587886332755445055385
#~ 53935415195230758699889959882512028522705
#~ 7528989392322215101563931396245685185
#~ 301153464627386708780887273262792222865
#~ 1447019058278583487014876666838646972760705
#~ 6752727999005617757947385377498566305370945
#~ 14470122821881303970212852593003903516440385
#~ 17725898762781984091012346574545217652360305
#~ 18328820233319147076345586200756572121975105
#~ 348247448911254732650694309663609737895193665
#~ 2781056315505833453947118778407199228535226914305
#~ 35226544511640968468117185376544271849238515776705
#~ 669304085258967607030755058322994491065268503830465
#~ 1854038026010241728825908190563688431905808863105
#~ 2781056315505833453947118778407199228535226914305
#~ 3522670947102306834044087248682007865838761355265
#~ 6303725815589082009407719012212540255727015508865
#~ 66930721948600780832334891457178146355290956057345
#~ 101972013291534148041916651677662854467882958392705
#~ 226638977350964872855547834371681875658821442846238952260865
#~ 4759416662425593070513704994787452216628205301437173145400065
#~ 11188420062660109059016836239101375905
#~ 5821477606342877287368646390305

# 14470122821881303970212852593003903516440385, 6752727999005617757947385377498566305370945, 1447019058278583487014876666838646972760705, 93097233462972639976350893358610352249916692242603905, 19599419160149492611672840593470043489539060577922305, 4899856299584863138737230040441981737463534244985985

#~ 1.3331 record: 4655734127045
#~ 1.9036 record: 221776809518265
#~ 1.9106 record: 3274782926266545
#~ 1.9449 record: 4788772759754985
#~ 1.9452 record: 38353281032877674865
#~ 1.9452 record: 2638294879881771254145
#~ 1.9454 record: 24773130788808935997465
#~ 1.9454 record: 429388072625313108651345
#~ 1.9459 record: 633708839387221385771985
#~ 1.9594 record: 4426632427184293146004185
#~ 1.9786 record: 30289748358904212366572385
#~ 1.9810 record: 1370862939340854730059272985

#~ 139919773284892603401054736144065
#~ 303158659430755143165760511885985
#~ 932794363136224939401054218319105
#~ 1399191180695832195871642149010305
#~ 1772308634743518001048112493563265
#~ 3171499087422339770459876285636865
#~ 10447289441352212971401048004419585
#~ 14551581435876756828342221794502145
#~ 29103162143736503230224565232067585
#~ 33673850955820654343636326952841345
#~ 51303650659573808638224550732968705
#~ 55221383927074509592577489350774785
#~ 268914750591474077221158519544737548865
#~ 340625313437260955175439884475404590145

#~ 165709828801165348659987395193678463554945
#~ 3406237183594896860092389411741603832065
#~ 1772308634743518001048112493563265
#~ 1399191180695832195871642149010305
#~ 728017010426459878356936705

#~ 3406237183594896860092389411741603832065
#~ 165709828801165348659987395193678463554945
#~ 340625313437260955175439884475404590145
#~ 268914750591474077221158519544737548865
#~ 1254930372392549808980688228520895523585
#~ 139919773284892603401054736144065
#~ 303158659430755143165760511885985

#~ 728017010426459878356936705
#~ 139919773284892603401054736144065
#~ 303158659430755143165760511885985
#~ 932794363136224939401054218319105
#~ 1399191180695832195871642149010305
#~ 1772308634743518001048112493563265
#~ 3171499087422339770459876285636865
#~ 10447289441352212971401048004419585
#~ 14551581435876756828342221794502145
#~ 29103162143736503230224565232067585
#~ 33673850955820654343636326952841345
#~ 51303650659573808638224550732968705
#~ 55221383927074509592577489350774785

#~ 218924994654832550816515785
#~ 639279061696677004929094997372145
#~ 1132535995673545452074924146972665
#~ 389070990460152895292891577255663796305

#~ 30289748358904212366572385
#~ 218924994654832550816515785
#~ 10300141479743074871884756785
#~ 22472137786063822097451514305
#~ 82493833111262286648925017091065
#~ 639279061696677004929094997372145
#~ 1132535995673545452074924146972665
#~ 53284372598621002891913195372701665
#~ 116252166558593996496051152805682545
#~ 229081343587719621485049462727091265
#~ 5010766391791082887389992186484728865
#~ 10932144280887665453938956611980148145
#~ 426754540142355612161332781739967634985
#~ 40131228031854782845106447421556193479785
#~ 47011423920882244304476778674633910552385

#~ 728017010426459878356936705
#~ 76318017347929116984103462366785
#~ 8216737111818541950499230458667585
#~ 180959983027381004190174576987837099105
#~ 1330855027023388986575946928980782761705185
#~ 29309870794777798249480230836165230201239067905

#~ 29309870794777798249480230836165230201239067905
#~ 966757480678274985995212386746344614930235396545
#~ 58983382439441107063131597946401884975171745
#~ 627227909123642420730467818700818759298145
#~ 1330855027023388986575946928980782761705185
#~ 98146961330939366255341286595569617031745
#~ 404056476533682721025625613232007531274785
#~ 28005842179161907229848058562567005164545
#~ 180959983027381004190174576987837099105

#~ 404056476533682721025625613232007531274785
#~ 168733432314256365975822626825585985
#~ 76318017347929116984103462366785
#~ 728017010426459878356936705

#~ 1330855027023388986575946928980782761705185
#~ 43896954104021088455373482654504929963842465
#~ 29309870794777798249480230836165230201239067905
#~ 966757480678274985995212386746344614930235396545

#~ 43896954104021088455373482654504929963842465
#~ 1330855027023388986575946928980782761705185
#~ 88338527657562766136835121106422084913985
#~ 28480146561932233988453007412720345665
#~ 4456497873665944483494630908043512865
#~ 8216737111818541950499230458667585
#~ 286262926807330411545250286926066785
#~ 76318017347929116984103462366785
#~ 728017010426459878356936705

#~ 88338527657562766136835121106422084913985
#~ 2678221667369461615815471378693802292865
#~ 4456497873665944483494630908043512865
#~ 76318017347929116984103462366785
#~ 728017010426459878356936705

#~ 728017010426459878356936705
#~ 76318017347929116984103462366785
#~ 8216737111818541950499230458667585
#~ 180959983027381004190174576987837099105
#~ 1683397025406680920009273481912611765185
#~ 1330855027023388986575946928980782761705185
#~ 37074022571292412087167242940541642527847905
#~ 43896954104021088455373482654504929963842465
#~ 3991554127476330332463919727683799211932494305
#~ 29309870794777798249480230836165230201239067905
#~ 966757480678274985995212386746344614930235396545
#~ 418434587081270374809891647090482893659877246461985

# 4941808546075660419264067599369649016479539371630778521435976705, 20887753712520609532567846922583920638944138819042665757801755042611335817254465, 224906436908031007079087447570104271409064434499731585, 43225442828665203343551053810841050234922320859806912515905, 922723577834882097089155855930848203988124904422542752754582465, 827588008789372248232972619716809961612337262401865327317326749111105, 177341012594819494885856131418917508869089689755681759280161467695745, 555385881837969384461386805114747741697881330167516065, 8912541157773704856248850726153279748167674593185, 1712928022736001657437035367611577294639589883088004705

my %seen;
#my $psp = "4788772759754985";
#my $psp = "728017010426459878356936705";
#my $psp = "1370862939340854730059272985";
#my $psp = "45737634436431198836267992527251680040385";
my $psp = "45737634436431198836267992527251680040385";

#my $psp = "1455392118896988500001436526865";
#my $psp = "58214503455693542735775164751585";
#my $psp = "5821477606342877287368646390305";
#my $psp = "7528989392322215101563931396245685185";
#my $psp = "1177059715761219117658883587886332755445055385";
#my $psp = "53935415195230758699889959882512028522705";
#my $psp = "6303725815589082009407719012212540255727015508865";
#my $psp = "66930721948600780832334891457178146355290956057345";
#my $psp = "101972013291534148041916651677662854467882958392705";
#my $psp = "2206948942280833820386780957648323379377299669825663586360240675585";
#my $psp = "226638977350964872855547834371681875658821442846238952260865";
#my $psp = "14470122821881303970212852593003903516440385";
#my $psp = "1842836800348739399588385";
#my $psp = "18328820233319147076345586200756572121975105";
#my $psp = "14089090063942564942304718922492104414299518785";
#my $psp = "156693987228084145384168898338065";
#my $psp = "13619855197403642505743435147863830105";
#my $psp = "30289748358904212366572385";
#my $psp = "1447019058278583487014876666838646972760705";
#my $psp = "639279061696677004929094997372145";
#my $psp = "2632787600289811236737758837545";
#my $psp = "3307098624318336884912041438460661977505";
#my $psp = "1132535995673545452074924146972665";
#my $psp = "609299754103181490100455705";
#my $psp = "218924994654832550816515785";
#my $psp = "3278282922943952669012673870465";
#my $psp = "4899856299584863138737230040441981737463534244985985";
#my $psp = "19599419160149492611672840593470043489539060577922305";
#my $psp = "6752727999005617757947385377498566305370945";
#my $psp = "389070990460152895292891577255663796305";
#my $psp = "2797148676542619034911260891148907665";
#my $psp = "1455392118896988500001436526865";
#my $psp = "17725898762781984091012346574545217652360305";
#my $psp = "6752727999005617757947385377498566305370945";
#my $psp = "7528989392322215101563931396245685185";

if (is_pseudoprime($psp, 2)) {
    say $psp;
}

my $limit = sqrtint($psp);

#my $gcd = 7313655;
#my $gcd = 4381310850645;
#my $gcd = 174766108521378405;
#my $gcd = 77728835801292945;
#my $gcd = 113375180882140665;
#my $gcd = 495088126122885;
#my $gcd = 34498510635;
#my $gcd = "19976310800932286865";       # record
my $gcd = "7051637712729097263345";

my @squarefree;

forsquarefree {
    if ($_ % 2 == 1 and $_ > 1 and gcd($_, $psp) == 1) {
        push @squarefree, $_;
    }
} 1e6;

#push @squarefree, grep{ $_>1 } divisors("6283365899669117794965");
#push @squarefree, grep{ $_>1 } divisors("19976310800932286865");
push @squarefree, grep{$_>1} divisors("7051637712729097263345");

@squarefree = uniq(@squarefree);

foreach my $p(divisors($psp)) {

    $p > 1 or next;
    last if ($p > $limit);
    next if (gcd($p, $gcd) > 1);

    my $n = divint($psp, $p);

    for (@squarefree) {
        if (is_pseudoprime(mulint($n, $_), 2)) {
            say mulint($n, $_) if !$seen{mulint($n, $_)}++;
        }
    }
}

__END__
foreach my $n(1..1e6) {

    my @copy = @factors;
    #$copy[-1] =  3*$n+1;
    #$copy[-1] =  2*$n+1;
    #$copy[-2] =  4*$n+1;

    #$copy[-2] =  2*$n+1;
    $copy[rand @copy] =  random_prime(1e4);
    $copy[rand @copy] =  random_prime(1e4);

    #$copy[rand @copy] =  random_prime(1e4);
    #$copy[rand @copy] =  2*int(rand(1e3))+1;

    #$copy[-3] =  2*int(rand(1e9))+1;
    #$copy[-2] = 3*$n+1;
    #$copy[-1] = 1;
    #$copy[rand(@copy-9)+8] =

    if (is_pseudoprime(vecprod(@copy), 2)) {
        if (vecprod(@copy) ne $psp) {
            say vecprod(@copy);
        }
    }

}

exit;

my @psp = qw(

4788772759754985
38353281032877674865
2638294879881771254145
24773130788808935997465
39898386437874778336787265
85866492509341408342261785
198408004487570768403697185

);

forsquarefree {
    #if ($_ % 80 == 9) {

    if ($_ % 2 == 1 and $_ > 1) {
        foreach my $n(@psp) {
            if (is_pseudoprime(mulint($n, $_), 2)) {
                say mulint($n, $_);
            }

            #~ my ($p, $q) = factor($_);
            #~ $n = Math::GMPz->new($n);

            #~ if ($n % $p == 0) {
                #~ if (is_pseudoprime(($n/$p)*$q, 2)) {
                    #~ say (($n/$p)*$q);
                #~ }
            #~ }

            #~ if ($n % $q == 0) {
                #~ if (is_pseudoprime(($n/$q)*$p, 2)) {
                    #~ say (($n/$q)*$p);
                #~ }
            #~ }
        }
    }

} 1e7;

__END__