123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512 |
- #!/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__
|