| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418 |
- #!/usr/bin/perl
- # Let p_1..p_k be distinct prime numbers and let n = p_1 * ... p_k.
- # If the following conditions hold:
- # a) k == 1 (mod 4) or k == 3 (mod 4)
- # b) p_i == 3 (mod 80) for every i in {1..k}.
- # c) (p_i-1) | (n-1) for every i in {1..k}.
- # d) (p_i+1) | (n+1) for every i in {1..k}.
- # Then n is a counter-example to Agrawal's conjecture.
- # Carmichael numbers with all prime factors p == 3 (mod 80):
- # 330468624532072027
- # 1358406397003392026912594827
- # 194462892367341977828363075381947
- # A Fermat pseudoprime to base 2 with 5 prime factors satisyfing p == 3 (mod 80):
- # 121831680646636291086639154608688151372970242384165493441043 = 120163 * 365412643 * 10977269855203 * 450068064063283 * 561608103061989523
- use 5.020;
- use strict;
- use warnings;
- use Math::GMPz;
- use ntheory qw(:all);
- use Math::Prime::Util::GMP;
- use experimental qw(signatures);
- eval { require GDBM_File };
- my $cache_db = "cache/factors.db";
- dbmopen(my %db, $cache_db, 0444)
- or die "Can't create/access database <<$cache_db>>: $!";
- my @results;
- while (my ($n, $value) = each %db) {
- my $rem = Math::Prime::Util::GMP::modint($n, 80);
- ($rem == 27) || ($rem == 3) || next;
- Math::Prime::Util::GMP::is_pseudoprime($n, 2) || next;
- my @factors = split(' ', $value);
- if (scalar(@factors) % 2 and vecall { Math::Prime::Util::GMP::modint($_, 80) == 3 } @factors) {
- push @results, Math::GMPz->new($n);
- }
- }
- dbmclose(%db);
- @results = sort { $a <=> $b } @results;
- foreach my $n (@results) {
- say $n;
- }
- __END__
- # Large terms:
- 68435117188079800987
- 9045346861220750863147
- 70335238158892421125867
- 87593819813773272093547
- 143568240855485868765547
- 164853581396047908970027
- 243481000190529373149067
- 267760547914370791374667
- 335097805698069475078907
- 470361680578357464725947
- 522925572082528736632187
- 832560021348422127426667
- 1820034970687975620484907
- 2149046746349460801430267
- 2605157947467797996807947
- 3365304608236039495951387
- 3859353924864097020236107
- 4263739170243679206753787
- 4360728281510798266333387
- 7900613872696016787189547
- 8595345112954412159554507
- 11704521751549958367277627
- 21515574392553806900834347
- 28541906071781213329174507
- 29431237363857685816007227
- 33833150661360980271172507
- 34429703849971249127950027
- 36100943328465990644496427
- 43238240218100484201369547
- 50018650056282930301051147
- 57666364049186913724122907
- 59539711277327870923212187
- 71003662684346882190762667
- 84444874320158644422192427
- 171707422464325875666659707
- 175352076630428496579381067
- 176672022178655724505204267
- 221081948731696270871926027
- 228523370315602155990347467
- 264079793768034374742613387
- 270136290676063386556053067
- 482001813895761038535119227
- 533966734737182516824412107
- 560066203274245940869779547
- 596059132007430984588188347
- 615437738523352001584590187
- 706818890274970430908597627
- 801739996004369134619912107
- 894445412046708642512902507
- 1358406397003392026912594827
- 1536486018499606762223955307
- 1815321619539652382319497227
- 1837130267804044793751812107
- 2023623971222499551187256027
- 2619423481524457814188669387
- 2651791873888228770082194427
- 3408560627000081376639770587
- 3688651964985680019488420827
- 4081749303988487175194521387
- 4391047159586605999625716027
- 4655359269748391913551305387
- 4687822090078157049203939707
- 4813941200693026259680403467
- 5762886571360861608394936747
- 5976660612741013874144163787
- 6967854626910554277690123787
- 7561949388208160365888616107
- 9537445336204414055092159387
- 9759314949604031643356504827
- 10211424373781434897965039067
- 10626456842160791277843447067
- 11260257876970792445537580187
- 11274104579369110225450868347
- 12059880431783093979950989627
- 12189191505056700686401395547
- 12551094196754024921403049867
- 13250862924216177986720216587
- 15229587851188341554449842427
- 17222637016345201396446167707
- 18038503407552250665853993387
- 18197727922992935751648749947
- 18887237172079478887827208987
- 19470491687991007084482569467
- 23976880743114436461734144827
- 25102486204818068120581383787
- 25556087928963002195904211387
- 26877586214793730440180570907
- 28260047594389449657211294987
- 30405738236455014764072059627
- 32206753839720498687161984747
- 33946276393541598133240210987
- 39323404773648619691409896347
- 41613809868072287191858769947
- 42269387393663773527797627947
- 45381726063201413635153012267
- 46722900381132133533985498747
- 47097215087330707651150269787
- 47524395368130435867023008507
- 50178655544981494493786731867
- 52926825724005241779868963867
- 63039498314030423521426642267
- 70144196069941598894345272987
- 74495465218970377841884647067
- 80539013839535604667400412187
- 98840688110829294801402891067
- 105559187481858803791971361627
- 113889468211854482561385198187
- 124356070720998450755736937147
- 130797127166536351738398670987
- 132673467351775248997835724107
- 134565051916597463481553434667
- 138107551003803043541406862027
- 152678824206282525141363852907
- 162533798411310644354045772907
- 175634237891853205103641114267
- 207482761595366334653921884267
- 220047152103707967097522147147
- 223292473863558018144247048027
- 239439709215397066278294864187
- 241274292415248018981040091227
- 278046325191879738622053799147
- 286407527500073729283719401387
- 289090629579189923807673057547
- 344180551486551582621442189147
- 350457393954193118938048081627
- 353697287363995486032595122587
- 471869696049612105211164125467
- 488473581221954149139141030747
- 676094606135994032744383760827
- 749577176988878124111649022747
- 789987760288757621810609174107
- 825895112165258493827896680427
- 1309063472737604026836834163867
- 1333005715546010658798779135707
- 2011438193706072134526587366347
- 2091644105799146658205529323627
- 2635198530795581839200883036267
- 2698268508615793452681755158747
- 2744049657285237394380190449547
- 2858314843683020711670415037227
- 2999407457050751993383031840107
- 3486656945342977784275232731147
- 3729254181470993091190597868107
- 4323790077931048637049074997067
- 4337152602903217144146045747547
- 4395952000092233206483760166907
- 4589810969811252566116702180267
- 4923936964099170022827875218747
- 5167062603096851770111656563707
- 5269928298507102691486455889867
- 5551440642398572994697586118587
- 5931532300859929362677162828587
- 6698308804555252158866602377067
- 7392486814714101714348005738587
- 8020055409838101367610661280027
- 8416251237903450514903799333467
- 8705236063214661889238549798827
- 10395360055073001859500069701227
- 10400512181722974650313557649067
- 11177615882646176430262251642187
- 13585739431928040667999968107707
- 14941624360783434580315298403067
- 15821284354583979879248800820347
- 17063871452163574624071849818827
- 17334361425463050679308487636267
- 18254110716595561191226116391867
- 21391062724320944516838477402427
- 21783266194855114941625027041467
- 22067497585080878986240641017227
- 24590164743081668680873294621867
- 25717575862911759354809431930027
- 27261546377394857453758963557787
- 27912168181207186826086081681067
- 30584381350090257406561923257467
- 33276534739605513690592051070587
- 33591100158409322318627953353547
- 35225328892327637079553516870507
- 35799318224506829477121174403867
- 37607874227403633801327635087707
- 38430913622093366764535981012587
- 42160816133924659750814184485467
- 48670924289653500120090032644027
- 51635062785591698017010519603227
- 54925014586258353195676075467547
- 55248286671934178004267936963787
- 68474933133835163056391395969147
- 91458408296024784603898764567547
- 92629371670327517380545995358667
- 96723114302350464224055267330187
- 98667106058556213022561527071227
- 99196504799303045899264041291307
- 126577200747167414902299139123627
- 142167805304648854052568799097227
- 150014534289349754528191947506347
- 162129839319011256486903911835307
- 173568145669586946466122338156587
- 194462892367341977828363075381947
- 206304054386579576341643791463227
- 229429513691051285547355487700907
- 280476977578312307236053465624427
- 300768869523987466561946236669147
- 345717376986053822401713912849307
- 414658275351086022782355397982107
- 442839655570295024700970861576027
- 458282251188485385511385408778907
- 546419472269316354956578263798427
- 612606598789553280523019043968587
- 628863569813718332078636698983787
- 640000037564716254836036890329067
- 710022669285258155894084780199067
- 738947918193649829329769905130107
- 747592822470126405563625924591547
- 755185965886577202237505993992667
- 786210379368657981081111058822987
- 797894105629283052815217244970827
- 845079274754923357898882440148827
- 1094219379605472528291464401109227
- 1251862366501925028458085888089227
- 1345456455021991863849834333685387
- 1408863049077559019701009279150027
- 1612656512173149658186839806008267
- 1808495952522729686238988884752107
- 1881750082592741664546466488481627
- 1944508311495820139081874649530667
- 2426506221045160095747173061601627
- 2566012354758286283788792633730347
- 2742412319560898898218756902912267
- 2946568408002988456887449819182027
- 2967365938620486959145141445227307
- 4469121796803755539832113113728107
- 4538205195003463689143207571318427
- 4893963115775302956048297406740667
- 5487159270130488510568295190835387
- 5489862206694866351393724555420187
- 6727113172793111588530087835299627
- 7600338228772653307104492177864907
- 8266927603234967224161673658298427
- 15773525900163441781756393474200907
- 18690220442873831573763412305318667
- 25518910755983539249209123460138907
- 27571841024909344138702942089621787
- 35767515776336486441794927621359787
- 36020629240784273504534127669074107
- 43695897287642288996190843022354747
- 51136900301252933411702510323585627
- 58528991918330191797325764864970987
- 66592847798631095322810098574100267
- 83494712161500444107047218738656827
- 86480491452525098398572600381730267
- 108433543307514226302958306002244027
- 130180240952697495904800834240734827
- 133821300239684360736252644872482667
- 170552917495235874158626978127000107
- 172984810849424324762378882128710427
- 190396974079269426009063603932421067
- 232811018206485989295674832899151547
- 234152953348022502725277795404949787
- 284750126190279772046593069630281307
- 285153731222819008388631605358959947
- 300487571294121915406875103743003067
- 520398855012510718909216488416926027
- 561148536051080141365274673553230187
- 565809263979301739072426102457987547
- 599560312440201267491236428174127867
- 1062786977228478694479531113234998747
- 1112978788534539481233247602656645947
- 1144608868849607279387313661976888827
- 1463410133605023433177083762522668747
- 1657725999727963143759627502589518747
- 1733236080821264822430016026809423227
- 1789193964491133130497855912644047627
- 2077239295163783831955475810954313227
- 2118809348128179868095547676520693787
- 2270416716376876097865905317425502507
- 3564678402153467597009712737008591147
- 3817335039803602623515571575603132107
- 3889574700231196618950977702240482507
- 4611899725645331135484932892396314347
- 5704824848146777528756530624599705947
- 5840631861566338554414545306296905067
- 9110327195790972519806517273647708347
- 9948518350017479225895668647848731947
- 10287927036337801458583696631096261947
- 13155270634594728000203114097497140267
- 16835682706680004631856063013425950107
- 16979610282130799873691895318594844107
- 17186723157944297837317253317865099227
- 18161863735887497909586060895673172187
- 19788767953972394762060607068480717947
- 22671572241434885951766851351324607067
- 23744151985580497625531517179564645227
- 29857466643115284005005539122178688267
- 33709150280466595775751037567891185547
- 36950917133948538657337202740356491467
- 51177718298483881344103782732394787467
- 65467453161151866487578707790498831307
- 69468456685179147370864916310349146667
- 69925959340410012383850804820723112587
- 83021349313256741919945700532411320267
- 134417527688607330219566014114306497307
- 136041910606897673889118324344169062907
- 171709158807103345247838932669061732667
- 177985445353012310295551927467711280347
- 187152315448955632561506299668782209947
- 187529081735311932494084450182042115467
- 201252221218667500778582008333718065627
- 206950290600826298990927343300766066267
- 227802448978147070312636764065297243787
- 276156403408517422813558816669841928187
- 329787065971878801867859922230235530267
- 338232902333986596568237865271955017307
- 365807964135148271872125311645400662587
- 371322134240355544149847306798533548347
- 394174648214260169967912735545134824907
- 442173220927955751562626240479207542987
- 469001343906370045168223301796040765467
- 492376920895221846841896913726955086987
- 542803006449436961232209382250545236827
- 552154426609865293362856821483132735787
- 581284113904086154346088397068397040587
- 613196247538565229767563636435952707627
- 697880965260408905036690110028290674187
- 720790515074128308445793394037533193147
- 818648680412181200692097304025291488907
- 874291646625077394331037199170277848347
- 980807007578394453772881418272194255227
- 1034871069706942603225661887894535228347
- 1515834240327990618475399415220106382587
- 1809095680925910345141579827902504102267
- 2500253757671125742642567721287020640827
- 2926294517956266929540521236583644030187
- 4638698299713574777754341609182957016747
- 4671119479972759512190083808429697851867
- 5016401360397029998876928037054465279547
- 6294563838426330438958714257489083916907
- 6755735188355794892569938121545771785947
- 8083224020214903588376560879818854193947
- 11109042669094674473252401978626065813227
- 14689691478923833346996919587161707701467
- 16086391305527453926905019142561192320267
- 25427830986886285443110990874262040589787
- 285837430125177875337407905992480883035547
- 4987907302758736994622148510194614517951642187
- 377554215320518336098718048365615062191243733467
- 8455815296459309007028238231947968764699701575547
- 8633135194947460439082492928941395800440787220507
- 6677381841560475568475381858135041590681358196918347
- 121831680646636291086639154608688151372970242384165493441043
- 120051749507432728558432408124149264824699469166213421449112163
- 209049726214423972650644255886235335009269075962644824906422805829521876803
- 1286243694723516727213368443559530030349949003135449627873454306561721509603
- 146514041087757753829845217182294094783212145787671259314683616591865804391227
|
