experimental-projects/pseudoprimes/programs/lucas-carmichael_with_n_factors_cached.pl

#!/usr/bin/perl

# Least Lucas-Carmichael number with n prime factors.
# https://oeis.org/A216928

# New terms found:
#   a(15) = 6414735508880546179805759
#   a(16) = 466807799396932243821123839
#   a(17) = 41222773167337486494297521279
#   a(18) = 5670586073047883755094926472159
#   a(19) = 247499293142007885087237709213919
#   a(20) = 202003815733964076599064812732611679
#   a(21) = 17988631465107219093106511654427868799
#   a(22) = 6260401580525839547593293275046894535199
#   a(23) = 521027978053852870937320124850878216361599
#   a(24) = 257685984879302905034127894788339525937551999
#   a(25) = 39355410745046203120019553518734961968898942399
#   a(26) = 1422206796849165887380738983840035626943341276799
#   a(27) = 438252156495754541448512765942687553061536148703999

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 $lucas_carmichael_file = "cache/factors-lucas-carmichael.storable";
my $lucas_carmichael      = retrieve($lucas_carmichael_file);

my %table;

foreach my $n (sort { $a <=> $b } map { Math::GMPz->new($_) } keys %$lucas_carmichael) {

    my @factors = split(' ', $lucas_carmichael->{$n});
    my $key     = scalar(@factors);

    next if ($key < 15);

    if (exists $table{$key}) {
        next if ($n > $table{$key});
    }

    if (exists $table{$key}) {
        if ($n < $table{$key}) {
            $table{$key} = $n;
            say "a($key) <= $n";
        }
    }
    else {
        $table{$key} = $n;
        say "a($key) <= $n";
    }
}

say "\n\nFinal results:\n";

foreach my $n (sort { $a <=> $b } keys %table) {
    say "a($n) <= $table{$n}";
}

__END__
a(15) <= 6414735508880546179805759
a(16) <= 466807799396932243821123839
a(17) <= 41222773167337486494297521279
a(18) <= 5670586073047883755094926472159
a(19) <= 247499293142007885087237709213919
a(20) <= 202003815733964076599064812732611679
a(21) <= 17988631465107219093106511654427868799
a(22) <= 6260401580525839547593293275046894535199
a(23) <= 521027978053852870937320124850878216361599
a(24) <= 257685984879302905034127894788339525937551999
a(25) <= 39355410745046203120019553518734961968898942399
a(26) <= 1422206796849165887380738983840035626943341276799
a(27) <= 438252156495754541448512765942687553061536148703999
a(28) <= 333791863958043189671786617765781459382301668208175999
a(29) <= 46521156947634673750957825164223546441200487134525859199
a(30) <= 19074090435451829746746984053080361421706952409259779667199
a(31) <= 3532037553146436562783521728890404729368163364907619947395199
a(32) <= 765881596754684241380045525579098611589814471468465029532759999
a(33) <= 275114850916952422937505205424521323097783162400484048783681267839
a(34) <= 99955119012110217537288587166217937093673720603174918405034884380159
a(35) <= 27216112313596458952695010988196606980991999599340735144892271012553599
a(36) <= 1040086557273421983686358821512639927160928136627395362865430481587758869860799
a(37) <= 315217716183341323859910896196993408751181889972749312674430718190733332175504639
a(38) <= 1362300337765939230154770298580699275493835560634674832508151694493670103945551073599
a(39) <= 539110270615999961240806236240526120563881827070862880639695808523899611325507710339839
a(40) <= 728424580384493134558681774854605572736062218430640729753538407830091750817493895766830399
a(41) <= 1677879201901024688938633505097585449383682501411563061008557286933924629454590950176898086799
a(42) <= 1713063790404263858772540340152161898794165140736698823165040100529360288493060495638769187243199
a(43) <= 2287142487518508961941813089354164979564835983341652065188146161345710657929060864917661228809919
a(44) <= 115857825164690715506876901597204757080616774653400880237421402744082401665704879170220286815775412589919
a(45) <= 96450993029537273001708845147426369398690626975982108276958198434048275661991553984014621357541451141353719519
a(46) <= 6451298263870900503749497146157630321732527706393352729031545827097561844857003303036034774225473745958119599
a(47) <= 758960636671784296588850680793435616361120214553055445970655226368870014698626377118327293580120897374152447999
a(48) <= 100834359541792757170828050017775028658532278550335402537038580228030062437910559187180118978260553968493166639999
a(49) <= 511120674175070141430286383405410291207685803748925006240396582618098385590953679524979826271574928031431606319515679
a(50) <= 1476196340145727735310118614150892751662441687908574857344312650518954626730170970564644391303937862913511951029968431693229439
a(51) <= 3790068531955503170848299313751354044900998845713628653216837555768782203363461030623467572471275428648212664032729327075199
a(52) <= 5035401768755126905863017116569223903057243852961136473436989869982665129018288938925401702427417265919719016571944270932639
a(53) <= 15591506996285442348500495285292722019842233390112181237864206927894646212542083192126984041109618975805718025675631720227732532952393279
a(54) <= 199265161628672581703540163194965337417880205080110203787779574662051361910728686133030523605221331039529645468898304455942293323326559
a(55) <= 33316039428773508467758204497062959367743758871458797232566642024531134006527264584906380448078051294383662173199147665175507929378741279
a(56) <= 8972413400020029662367713471241311650565205329947004776494279537835446032155228711190490606511510159608492325731567272503695986745346090563599
a(57) <= 2954605902787846489865904586142731788803946921506570486727522438552201692089179206417647791200539452120459283333342594015051489008309203677910399
a(58) <= 53362996495809562070573968708650315533964559561070408226420719789058453162710968182945984740238274429248478584643586654929295429731455554399
a(59) <= 1567955442874779621045831495387726461680855324628895767131923600174986187753035351836014522885934438742392376293228831084923035116386054205251073318029518411039
a(60) <= 88515524129116494917811247368652779806240047832877339806786020191517529515544877384570876322077788971709882578541962587193069701819442989817584884259207159649439
a(61) <= 775492815055319162220624767729569156988763029802344968263152965911806139222679014594393514052499716914491982147069370864040358706977499045752067889860508519467519
a(62) <= 630460314805239423092218738420436639870339797130112958128072426496815856566840321521376079445164855118118621833092278644820703884464685150696442985515312071188639
a(63) <= 271499000841899796387088560319622465743951361101708850981184199385292627836250337759755237821014291558456774502499215148045463465348370618007983984187594556578146272945912347839
a(64) <= 922591602887294755184193618575746213552444923237127934938214553062462628072944463154489514646829675368562260049437454492947744233576165530922239570702709453587276591298255759
a(65) <= 3458528108526267218243416242866259545607510410223467673418197427330743867147342634252172491011871023700099956548413053479697089109307006651073938386847579673166698486562243839
a(66) <= 213808397240047092779174115067395764475550558396401585611533647930565428859919652758962043140090093727521826842768180847919312771636508456841404018122222301769230526629636812202933713119
a(67) <= 969466216083580028367392877735216458589371681292798575943700523750561865685785306052045374427650820199109534506011578097009504115238459613164875327737371670172212408618967246477217633903885572342399
a(68) <= 2960016440139852566353421262278276141947162303442353272995099787050069533488502764445439913133299496234821700181305826448851073595949389967285545166455458504558291299216803089938669225830452442507060559
a(69) <= 40854121493231752429781563327570087974639225026756786164046995656590873732370461183817187536657118461790405132063279792429670341473385038396763601117104612590210716769463822283934611519
a(70) <= 39812751239134996864276184103475492709954786359098157777186131891996799616349311835634154561533811991761533355021701688543085835336916979325210545614230961001348852683823529855001755097099032092196799
a(71) <= 738538623909619260719061954312237208187522633362650660616331158132587369638662730397149155788513421990615220725931148257993027869477875166222561077154269356563484227331350588302241794178281178495970352067802208313420126799
a(72) <= 3937668102129683425261103891752320199101363752110571827552234102865688374902587778125824862064762530976605971802024065324502598394099569609649407774091120535150747459786815641622028484741774124726399
a(73) <= 499716031601271664031810127647741902494784268791888172631445583076994195697934591313135132148848448022465585670086961802036885622020484367547771748414164489172177908783436787558160645124282215118614161141893212159
a(74) <= 10224570918616329005046732153423594796986913665361206703004371570625514572369826365949088121048532266792383972734414857198864813370852434931983624207982608390957361342482509078244786742283865999704485003510369283199
a(75) <= 839300874580548254154062304497506940317726788055584420081581273144363341711386712922553294781201741856282627748705724643490660169067786252091821264581465894940607984827945465040135287408323378021934995199830411767736088354639055599
a(76) <= 36691899815446457361637526150925344152553048478868614547402368609317064833481291859781715556943934076584923053562983567434151359383623306240488013629543091196405834287867332069105828745007844715227471200044531199
a(77) <= 6696141547656275390160780719030840812997131610139279205048031047477235519954840494434251411303742455813759630677341395569203260552470989623432967095997658109296420479810065605806748324094678382255102424358097664472316299171873546293815673919
a(78) <= 3446528659092262829953157873447210447793186988925873247035524717685341685152155670879759871508331021792930950570506940057561975899046096080479496181694195482600355415192902687501146419629121380451117245831885519199
a(79) <= 2277087836641152255984274792817594473684533448742136413954300870668517093160203000168836867231177471787094832068069900385956861721279110970798453543441982939704276047106639686083901452756262106503926575051834897899209512120525695862708079
a(80) <= 15758419092617334712060503222576795332121922990819799590725549787912348549005189897521729747093832513353232947866992286503206564230268368801313908297755029104993008063497083862620872420882321960464975386056516413624139648843129317449878995842235359931999
a(81) <= 3681274688430004404727913833743667184352469489987627520330834294730577257273463574790252228004190679376527758181215253442931600728517195342875337081955875579497406029100951591033156780660930229976197838457589785494584226135185121250737355324170613999
a(82) <= 4661288255345447304046749801633017129990815362414352572895481754977136219670850677841288875037167940309570564725033252106397092975065045286998075335001548280957456860806631767796752552947565409266437336001388368041877203277985640395092644131432302137774172900879
a(83) <= 5308497565513847830076897395854469441308132331797181796958673000385845462812248184844214354137659211724849007304326350119304757797933514077260330871510259844324415807808492316294435117141539354381556610060966899630025504100081907514862415538836258962675777599
a(84) <= 5673842380688984965777890877236600287005371530091274700456422893224916339568931108825220846070178544891483550451200419620842592662525372102382761455854404152569277516506427908362871732169428640623936603615487821016477299141633061672674426879
a(85) <= 2261432464606868772265229088652738733402096246643334429196842670540198533974522381911248127613908180980227331192313255292639265759354022577305759738910812017467302293897302967509799715803138103065578683333302120310389927104676446130602177510577558416479
a(86) <= 6723620603192174449530915092092138651248259148772766302045348506013932212674510695004213209381547622671762139307546001863809504583052408797308744215904015459693977416936729986608083391737085518370131194731892083805770428859493544726164978614982321290145096114183471586879
a(87) <= 61393455734405224518522642414248815717669267283293269509332728283274215953297572798217613905196425684830981329486863759366249323468095082463510323576025913572677616559259911142929507032033464636966053228113622495892580157571072754482409391366595071973039339218674325798251791126399
a(88) <= 32182834892956171606633511288924547081627159915946188027255639221873065585072894718098406214142904258128370379134181612199194200287249245043348681828695814295967894886039918103290355478105482821131077776237848834378530626628220985265935067446464733265726423039
a(89) <= 73939392997456363630146424572988255303954442503527072219812742065164807069310798453595397233567236697675758303395240081795036202562763647879275836552132026863460469340447258543798397990359425298804552780249542864117974979760825800437670920377073167096487374004828015121919
a(90) <= 3061339237235340559968256778766376368557210521236822683241359539086756393937657077266543565841607231608162506022987036201159822029532608803464375351731075740297074487480457838008065114202077908341965189216535110228486343600141904557675857477487155663688692406503313518373599
a(91) <= 16171782685784799960288706609559206064561349098982272842248649103888502411942417221034490083331599570421612265341681621905639726810704160255665744752635527800967894794344165114025035652253255399063749818113186748588194156986408165087483148644054350262710491244185505441599492162965130675583475199
a(92) <= 39490046386964158219457107254810877014919659826707657182201707350701579179846002730675228166636990209769018807131232544794364736283979907436626832545811672080904410313210695783517921815138702249302692179465741297848535921932541348867093271632027373406009523317944488978285083159823128568027199
a(93) <= 3406141975535689816407935069185696241790557133216001676175874219592256052677598633472088727218487967139275079700792087213409876917514779375770257283551973662335969732153087444878529963153671209438910324105694878318710565211142848392021849691618584614047299960041061426532671269871508386502231199
a(95) <= 10207694831684141978527808566224680049088521333707660469152963500092147866293433680133322916219470123075995388619813996431413871126094660669963138582420244029639560572346366971676823464818600215358501457097527560560978051313877214005268541820381693839789140202202959875187948191058192297603873657141451656671830146399
a(97) <= 143721179913091569106846164030461708672131513600111690352143931734313843502898465521678428028153611375700651513269693593824251540276612137957555951719036432727547813120102879578982289672653851863231655458496356076706738257343841482191241882871876489921505621578677123809894488922438876600360599160663231705732652661379780799
a(99) <= 653625089448363119392316763306860428318105878826522620571005822295337710281464589836673463478169351857530152733727369572798827376140987967539931368654055456760612955570318432659217959696213945791370285792018956279174247015719626209098248614116808883427095314443167288950160552115752114397246486578525575341090261327940409022996883044799
a(103) <= 232295314706109054050525303457645296943909553186195224705322344977868403916097937615231989970712724952106885796591789266791044434076351197259636355730790851059896165852424404727075372892358816227316709466052841521385166162196375516006793132864586589968311501810549280492295950029785211158334604304545437075071891514576729011502222288799759
a(104) <= 11094888777846812374383397599707980640262649570592314493906012753929689104463760195421130021841223346362891774640196625421314651861676872342639971177778333839921259075993156671427326640723068719856425828525085118364933247415862115545273863668524888880710210938835626971785405365342626502138585460274659063856835090844464368912488774718079
a(105) <= 22154722255820002663559983903166335966016049236569789316063909711055504425573887461699364549708499091895439401927856842950260001515149001304947146271147242135092595035768907424058028281247907072752926671390429423752700421785423507769233224046700876991388323618717652596904356254986041957725291753061380702709945381290521540791863265689075184319
a(107) <= 2305798397332324643882687942876065691091416495768038202828301957984572131609696709285185037876425459103858532285286224498810691114321258329323592678145427000520874025492522502456997171954792336414224472686146231226771962863289611865982827797162430473257868840101751386161372443243090095877145715923247976950499538799922634464167417430691271455959319554799
a(110) <= 345744524773942671681854304871787175249705991429860264896699136176719513972998026265784373370379131117246878840095115053373310775311424156560699076217858788912792569781478248690518447932832611520016016578449129881403855288936255085397804599622075824005953237187757376114935671979654104381004943865004926222513502867251904089283871612865521275663474192734585734844625018570147102289179766399
a(116) <= 2937262310531690240977869173784388542022922357713361261496002762588423028436601182904212844529389901813682136043559766165926126865660138296102358377143339661199646023830669332699939731657989310893734285507054879149255314423121718787000372073799733366762098782909054579430720137378485222516374779972553986165509004099190007977345593295496299292297437466806424421692743155630369168881470122102223839
a(117) <= 911963730154442844317505074719683910927292601092353436238973631976732011458048915219475333636599125842049705835439728699035513879058667898385702723369987614441873815047528087551738470571759850272776596713660069538049171219777623774765933795789469220158190247895908167092008976606739321367424658354371482487661291895303013678513333952977603615128078625540306828237618866224406485285599
a(120) <= 14899811665949022127920063022155310505000494238478727939882746455233334784788724845078884987056299458538703536005730072553809048248969943657888087392261763314592730179486003736058655628195441576452964595404388739972552802702081352355859702334635990459837001585352814746784307319385392845898599034467861398741489733344004424519862047051275886325505769778275191616806301189761130599228679269541553233861495047914239
a(125) <= 2198262252097160628431744547105000874793047500677488027546376936203287235268126647906971678119505297872355942427211069228999513114107815850301664980029987677545671399316481771744117645937176295440068330445148203893310615817596215966190206070226628651013059973901557161632874424112903887830095292651987186339693209231862796077371365337706494946103414122272949984636565788125827319341121540719731838342747614731199
a(146) <= 12250853635460420197773249680031759171895356759965517995475447468297362737301220264337794095418107768286290426486281398941379963628537281104139008997955874877100243327046418096089943215412716035626198518816701442514504356160106253269823768151248364545150071480279369716545287214662968713421379175295019199928562311270867932680779706939522414361416990111024019465536062366704571055134391606996919132926062639006872293109897401103418064266016412204314531552777416165815910391174765978052314153120231417607173648288034917319514406471756799
a(153) <= 106421523160533892630885195639833457723748942347851295192230238010230099669651149376216857693740945702161968988609524347849863208760326766125648298342348054189907135657621540349424614587431755947540209946762936266291845107683947200123170264647123680065200003485961447582161800833994921592966703556299519487114920561515700744697897169244970071122227426042286477658847219276679263525546107082963769630184655570915216575449278971758577080488301370070397811186167222243691592699579370602109071254421960211136578571138549998754692515419413110160868860799
a(280) <= 417087935487143074010759494913665830869258942901267926396306277016880706436703489453249816207609861026061397306366792839474341175425130543145678096793314412758791827469178935236441808106718151771293778222140548543942801653972602644189305043290435208271680056525478628177625284766335096216726632802012880177466422259049799077851652730630398467029222083224540198532999024181874950360998874121604195674834159907946126731146304106493297895436227833115698101332309321963382636207017639709631243597732409259128460715317033948241950384865199246617176074448833213847605235831759624610015076363469984107057986027811765793414147445078671027923003805083349807686317855646596896112414314757429024901063282869367759459052944054857164978097392466771232554226955814504047727654424862999163338687326061055637433565436760884575404728978750727355545062053911892623493829027850908282401945051511970412239258174665372242157779113394858498361022069722785871113249231725845204741433022568464125635468506012126942690859527942285748567753486931118217145474813019602098018466105437764594252482193726455698151252155491892224938425585119620296121209255213563080418342469295452939649591693756651765660910124683999135679696446044565566039505599