-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcarmichael_where_phi(k)_does_not_divide_(k-1)^n_cached.pl
executable file
·157 lines (131 loc) · 20.2 KB
/
carmichael_where_phi(k)_does_not_divide_(k-1)^n_cached.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#!/usr/bin/perl
# The smallest Carmichael number k such that phi(k) does not divide (k-1)^n, where phi is the Euler totient function.
# https://oeis.org/A207080
# Known terms:
# 561, 2821, 838201, 41471521, 45496270561, 776388344641, 344361421401361, 375097930710820681, 330019822807208371201
use 5.020;
use strict;
use warnings;
use Storable;
use Math::GMPz;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);
my $storable_file = "cache/factors-carmichael.storable";
my $numbers = retrieve($storable_file);
my %table;
sub my_euler_phi ($factors) { # assumes n is squarefree
Math::GMPz::Rmpz_init_set_str(Math::Prime::Util::GMP::vecprod(map { Math::Prime::Util::GMP::subint($_, 1) } @$factors), 10);
}
sub smallest_power ($k, $phi) {
my $z = Math::GMPz::Rmpz_init();
foreach my $n (1 .. 100) {
Math::GMPz::Rmpz_powm_ui($z, $k, $n, $phi);
if (Math::GMPz::Rmpz_sgn($z) == 0) {
return $n - 1;
}
}
return -1;
}
while (my ($key, $value) = each %$numbers) {
next if length($key) > 40;
my @factors = split(' ', $value);
my $n = Math::GMPz::Rmpz_init_set_str($key, 10);
my $phi = my_euler_phi(\@factors);
my $power = smallest_power($n - 1, $phi);
next if ($power < 8);
if (not exists($table{$power}) or $n < $table{$power}) {
$table{$power} = $n;
printf("a(%2d) <= %s\n", $power, $n);
}
}
say "\nFinal results:";
foreach my $k (sort { $a <=> $b } keys %table) {
printf("a(%2d) <= %s\n", $k, $table{$k});
}
__END__
# Upper-bounds less than 10^40
a( 8) <= 25048700469284705011
a( 9) <= 330019822807208371201
a(10) <= 9645020063586019926451
a(11) <= 215945949866338108941286549501
a(12) <= 879945792420070842690876751
a(13) <= 140691049887970123821616185355341241
a(14) <= 14309679584735089932659013623215171
a(16) <= 619002772702320168459989066334154006351
# Larger upper-bounds
a( 8) <= 25048700469284705011
a( 9) <= 330019822807208371201
a(10) <= 9645020063586019926451
a(11) <= 215945949866338108941286549501
a(12) <= 879945792420070842690876751
a(13) <= 140691049887970123821616185355341241
a(14) <= 14309679584735089932659013623215171
a(15) <= 3695030263802579560517979598342367761699501
a(16) <= 1841818304380671292017309381022071653191
a(17) <= 36427467554279361941922778898099584218225458006989551901
a(18) <= 45357002660261320389121052802252374862822876694411
a(19) <= 67435981906742519252466288259272171393719883798625654334574301
a(20) <= 28726276997276206037891932223309403867614468578514071
a(21) <= 195685615507543733067637501783337589732936819649719207880121832342038855701
a(22) <= 23347528580044868180079994745941865572868261611735369830060798151
a(23) <= 283941671007889482337343930273307981691376387054775103321477931944837889176450501
a(24) <= 150615147040963544065779439863417081169746820158046691567841311431
a(25) <= 6160669429282722614403135668073222789153676161437098754585180789064644702852443951478969581
a(26) <= 3059924772127201430130346204174550644053694974823965147037392591182748091
a(27) <= 302279016038511057477899676605506189929281399009551780144495025888799464985043628943073356116336669221
a(28) <= 418138508935387307950554324941370025704963171960224063815936899486047840388843784231
a(29) <= 146563678191083105314956799725793057802555069772048787734778490267080938247437093006190576808812767001021
a(30) <= 52903042722537283977305601502920630115113619839341070467881122662715676841196877674830174191
a(31) <= 1747797997710515624747008123998612433412300164376949224303767515855057971925442045800385407881274180096684857213415519766367221
a(32) <= 534526486213888631559100339125599677787399134872082025261709977548958336901894789473241623353891
a(33) <= 5706376573111094565601177826633843671557473856488310595687362420042848254753313145423529612692172977318411779900991840454467664306861
a(34) <= 4779103855741399327689139131242577837043923123796058085031306256323943613511718635686315873944281593873013231360541931402795631
a(35) <= 4657522092033424312884163677964360793965630799382119866090345074725207042721234766112605806640007875198283585376638789326941035999449659167341
a(36) <= 1621078874398006202661296312859160633100589713096132551750953070322510422598483599387472665685930281390670092084918232174703436450542794357621748061
a(37) <= 470303727243164954927365323833495714843471128419537567679264816186544472608410607060518548268943865746366132685891414154768990235415393571677869101
a(38) <= 621436597757473721840344897221795563606916336883841328015862101366468846379243456060666252001873314172784848511273986088367724663094308105991610737655517974852970701
a(39) <= 23188193053854807838185997164906125752370313128915945941471155894399958057705492220927456325674251489199422300119020692542076885041527673820126569179983175299461858541
a(40) <= 16284606404346566484097613975293770018278549519463172063983048683166315204476801613387534773187212168178397919974174081684012054270144608916327676150340336674701
a(41) <= 76321261515484236682625585207656147924037258461459180736087437303949501304249741041032466800220703866280149557621395907013455821737376607628332990788650616461101544101
a(42) <= 442720630850469052156090936126830987531296288854720946388778160310066232487226169562935021358503565454602529727665224101115256873950704638997958434764009277682580914479182776101
a(43) <= 1232942120039668068029871820810208630706558996993869233731998928370727176726862741537195943397299365891179621881457818095881819173666381136400928746227061356596136940570376435854284087788555795502222529938084257013201
a(44) <= 89468820873487582397831754003441017427578191531595388338066099098284584236046825153059603532855255130255774366935470808662641660635841558706692459154394623205746165405489805335835659501196124024078073694463490181494441
a(45) <= 49870956935062413897545937169259507637603712832206124736068314210573802255727237041670611960910397228684137645080464403180387688666930364020820417906283620532006948837182102513939071867796216665416316616501
a(46) <= 238221072060663934853696109445091314913359350686113211603066250723783149952530477749287846822106493599996135161142826040873725968349747253712285710010424700871116688038404381963532763099370386877412485912359048710929052277642201
a(47) <= 81893472956020874578566590027840517080238921000019161776094521496909203514121015457610637068330397918976008441670364966266826767401492912388758237385223464301358690438834945904286414973379314701591697208492701
a(48) <= 14795117370399604562816451239540046004923195906738389649933887955898423320575046894495327341299959494113093981859933235762866633591335392763442888492120751302824588241276010033355625807890926976902594556336946620716853264575778087277801081815201
a(49) <= 35698566127907375572653293857314842780340008519183128084788420031847103563780297835521788640488084412616610601510213638105578068875034090147046984042530607445961822533991188926637086833180712102456284998141144964186176686506615331219687544739401
a(50) <= 7957178020590523707813378660400140300070797340588625599098596129321871842760950526358962811757010912536119201624927144088508474553449949195767803550082636828299715768117408540740570299462054588309199281627332600051820522580129659837508846092243571918907501
a(51) <= 932557857146823023653282910611266764886224623231124016578373958726758763623090274822651815536275206679004980310684635532455862615164883712364790625853197104072427680682356468273224925553867469864540957912011320610620783275650301
a(52) <= 3872947514518674584937166155078202566912643303857552072938324638710422845874884489260998944986934649863937673072895768077035890849008633737629929970300009662359852912939140956553344715776526395542865730286229709497828693488091362305370179787620858590698322039901
a(53) <= 84731553093551515799398759830172098322146202878915352880556132350228710577167397509862955069189160070258386825301848668831404248534688889554995462158702128543348065200523758096999358366641340076690181138588969727004407481223676302549897208734792758286072536595413111318720360329943522441344072114794961
a(54) <= 183839320875369510453854208639173093821127882671288540230956729115506447746294877503656918127030239510083474340551845005185179110635709552199577484358091211681513428712308613703108401911803905980053318351029146880492444185740618668508637818049870579932398283839487865032466059657947981387012729481
a(55) <= 41691318364038429870213833179407722016281712948003556802825064082462756433256821073482788294897376592394305185311203539030736801934599764409178085628233737885313801017731531257868145904062219555911114165319743777994881208804046294166560977553353326444474435245406712161376064180360015475750786601
a(56) <= 805095226669147323480175324308461038442554952966733136273324702598677180298540603436112097358858229158246265422406354297058975893332159892005538715928512580105799921560370000915591535300411091513389609239840456628767839412075623804897631376365324282916891848425045446527484558511254914822989882059285335915170128258269201
a(57) <= 122757180775570461174924384736523430319318301585201719887955579553690076139049412358476889411489695199518131905439141833663672319330544881874351075371828352669355003338488473794060494580577112693667932554645928476202429271427772191401749587637564535965093101755217417033456350556360663027941915239401
a(58) <= 609921872294303006497935511876959841489041927584807913195682282804656273682897958103800301804028472847286091261281006259268119732190231221931705294551014100644287433252194590232141654473343619831818969025927652798464375847224289082986278491162897150283065636775994227860307643919530013901
a(59) <= 75239413813435587443461939581908269556673657005982076458338455360710865768205445573725192636909496373098267457288843665284667055906669242052502436033738364634580586431684047321741268412270453569438531326249647459371494912209510231118244962292077449371587344407438725311368788490039184057428225488831385434357076753182259785513966161
a(60) <= 154980939160101799940823050913368666773470507139062635971964263994770070629166651974325851687669935735050753284616481462369444683921961099066591238616656366226317357393672721743420150209443743279309233918120606928588325665606184988138379548894003475521201397287144125095351787456525185058301481879813084249926137916312718698734937190463739033570550081
a(61) <= 4193247137803814347486004143655845357240839582821399489768171085570610599235768201390023232395412033750481457826130904595457922555658077911993669808253011801321705781621242172621639850988923313411686501422878738517379852500863664252060846915570290650273113259268784441443517725017075544575965630368829257162458656977400697957157218420526058127257020930400901565479634001
a(62) <= 205570543890573536605726402626033344130226930646343148442135050472054380313336631473883935597259494409600627078571433733043597638956587442496843901465536104376308970501996732309985560533039119267196830394141886135930156252740624006882791839609949972451556190108086511999985273179063221709238461358733564672903150430715413492637506552241273823974362801
a(63) <= 1474855833651590838621091612891985611329837728497695723276952858643748580699472308052413376967360158754740416628490952997584316318275841296545073197315787911114386210040573482887557899943862111219834446875128902907352857573720263376963959173628001145216417890808627126208207216961402637874194457432106577805995840944984071875445849090819397377023117603714697917053915091048401
a(64) <= 32440206585966473825315346622161126615859777133881795116561655208528857058188903459102494815567867217511084092238475871183013986606818131606552159414906535073899787072210743608328716687544152049531203046601991186407688639796800954188704404361139417534890848841197531937773243902451886020334398486456821760404851694065738391873198235656191059807185883099574089745281
a(65) <= 196259329867077206076099194917654678109213997623947642512254670788203339623947424127130186398955825410102238041371118380035410342907850133559453544632317066038728816675168816133962457005562529531651234128660979350527663980927429865761746903504924484442387396362109806056968714155959178949848464198911644927543143859831969053674294178589122448009193601542267668681
a(66) <= 109197458312228653731796105648156734418704557052723364416102361895457802549137680319347822497363352948321054812351939989071405149115532863212284187445767074332414812746583594249850563713114339648646185213647928316362427987779801959188855811408974352453870896865479882566246125578393747419815341234295597737264547765151033643011142834140764715926291175476919845761
a(67) <= 517105538131979824758758367043798078473692126391285459169539765188386530467730072615733976273364879057722054389997743959310390948607069792604463261038440563460592568781748096960940140297316374603669071828191897473963960318506968706312149880852882367413982409871939084661797820631064712868425965187233078535823741179209535363563053691648861858321412771607374460914346172025492442821610126223776298193791383544729213507258124590886651686140347391201
a(68) <= 2963910916917486264962364048417742606298392026706352978299396329985920435761120084869841018083653834611890882081504995436606291906387239916132608708083419582429911041926847587958743652887759471368504311137053516320944284491712464286918561087657149815266502434554623172489215186002715787753827543898936409295587981368971664212413000131371356549842961089245143200897238941608788680924161
a(69) <= 26890188013925987567275541193723409940671323279343770432895823744302239667075910310860875080360118246290469230545477690793560623548831941328768679212767974932521962356164618366324149977205849552948436264825994469608784951804945812336749142900663008647734115913591944568240102380787175587034028990788672879426934342149595381177790634218301141397272063713939133654071938655385584693376850305692592197221457625206244001
a(70) <= 98833289001045007618206660579022693664452642006956968306889419103305857956874506431083344106530286498494350495433062293399025982742833288417492597920412172405157422729731232310578842299203568729975589137356099434016388266864012432976399271234875689777802568462094128407179840219309959480904648028320435760133133119974991330135674520456487243665787629337551013578125980723998508158228577444637343967199862961
a(71) <= 2673216484741333404380138597717273544065622402233685183520831678376233831043855960849872671945330322423911183360278474381583783228613004191956724449215915729561226680560998534238478062589588991761217587714335304943093854377958129798146378545576969683698717083430178933208155898627363962473996397155349006144170956930641831017642318932602621923576563744954092263920539227414181664463668362950974925651748977817056957037206621642801
a(72) <= 94238025641967540527781258874409928673129784894232121960402423558466370576476931679112441318375550038126779613611264828631988152214707390319635529037928421143423855756364899469672260573669283898140933659683583001058322872415163158428128367273959038349413772708902046303961559272264252718864929192072244458837802290389176678830609840978626682975834055511958405189086908770400696128416020982046627794360592708463184821437859769692505883162251822395281890004632433543500748801
a(73) <= 2984693668728775318402218990758502691823089222320397013287297681751177992142378896057176568937971935269768682091536593505009442514305454000645214080230910333595633238413767166854362906231979549981388675745232960761929235443134237072623799423324525967235018290525944311053700894405629989843833313729228792344909574964261743817218292494338613681977717961913171030614000610370368375803205643288255903878049098983393789711959506424971121
a(74) <= 625262251459145789018473762344649813324347005611930696546380591725269423020933587299754929587965166376889434634670879916517034094799153866784486405954843694607217815046649971260649913624400894920523561182562217824048781900205015232335343409265764678656834973783363645197855792491234028029460486348007576193147528344956309209217031728223166212892225880544869703656126547710637140050085722809094442203940690127928531786549555081632142761479430917922581834310222733694554117841
a(75) <= 8171917794632503253992584832547457048915020932657317079685047632921026864734161160729500040096422632374690798827113200241773052974210585192130686909056547087416637755178834559245274380532757647330874228686436674491076773828123819841298910534437423313895292394315941046945314461632990820059541307261135947167554622203287245868312634117019881431668457323807821556582717142774468952538526938289850822843770466537698906020482835955104059245761
a(76) <= 409204725705570692267816004746056838852712026510725011544400975923112410304608632340526026178976720950805706742420806570537593260980182775633570588957545657418377412832694799279409461341480745837453306783319639080319632007580806388862477992430553683968031783581747348388705091778436884960051218436400900051148862558799082360761457627441673303055434572428870935631843348271800053595231722122361519964442945801104629415805988298397337948310254923833617345428316647758903488797101285018801
a(78) <= 15064672449198229284635297421768000416151645862699366631443731078096725807023156388904366823069054101134924327734272059757029850326294672914481544496124335069997398028557315751043115992298985234133740620860950309002294212879938995933632990486830883824620510470482930525621395102416640599775976468428892198786537452351822022556785917225038964571198614264839491302590933788252911884729997532460211315165693065119236310368851904704788765310028835772844841769152080911601
a(79) <= 6306876544735594093722362183177621062425593217480039512604847896860097423849340899517605465217379466822299529740497181009947136645567844813168891114739111296679976609256174655945325931073198897883901446209317711813545919439920373059842639149306235653152147741458505579471270025526042825403984316151037706298813848341728416313193515735447789027413688852514771053416088815910549698885312388874005419816779954506662178582133213038890086395945554478077481589609292030425589254636560785201
a(81) <= 2287903594876439323935329766870744284122078633664554975218687670800257912544879908085591207553982678514382437360379716150933410403343976164580672477047789196861207320327821053201287290821289149383456510644512337324865670435886126875932508492886169772225595580304527605331426595692478448623758791675394410503288032587665633668972031159517793977876688903433775206550838896370395333730870665647773693485317227578025836224379400906540284551596812177796390056186091229223292577210287560644243398125160861160332378353778875481201
a(88) <= 634264062670966012563196554174351757730015221073911237286698183537035266898770245488724190225602483182388213356540742823493501217792960342846199161273571176333158190492563321238260199971588633625363954207807652039830848218802308145901436924046778039341289713608095639548519432226110576292216746734953556918719535773233584986739380078090074706070195806292157894979067383114488749045004716244061683979435893029573391227185328614098862654613569029007939860517338827766210005923690632108419610987328149968140303732152138064081851018118972569905825802962258917323077458499579855842088278430578284375491599374729470031375936795323302664799362271972582125674992481
a(93) <= 5704709962974502154594969472930800694452107603894688816444375012002844976808871985700598908782409763342655914618748486118241940172447635629748825018799220603589118140540597502138373924419105503083007137159651580808073970327984983486590843385418289588943506994484780178710011459372838969369697363973843226578094674154890882626797695709088285154145792701610701148684053353671982143779727800094003161089800763520734443484594157705112003619738011495958073463869848981073501317472842633779400294568462409205864559352127827311825055187513109457679643970515252519242522412267159420886918785578725199582785430105781708511134247250346493630105932932649055191134644175646841052703758207324471786607625922524561760675189821580231116806401
a(94) <= 51613198363225827414540600265966976189369848632670914608718729989160398230178078718200933052265333962846379602300130001901377132266817402078614378831111568791733626264741121097522829318713071655729367410894832501721990505695561819891363711500904672118675860814150183647080771665922070698744697567415505571848518863825805452626506378969880168892745996089591108755934116949102858023406841625320564481842723082885656954953255093354018548123533835438353883583191846273506628354484804475372038234561636832401129018323145192101302604213494638000182007963202362065620853947474632182420748136486190999286945914682480871717091192051452001