lucas-carmichael_with_n_factors.pl

#!/usr/bin/perl

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

use 5.020;
use strict;
use warnings;
use experimental qw(signatures);

use Math::GMPz;
use ntheory      qw(:all);
use Math::AnyNum qw(is_smooth);

sub is_lucas_carmichael ($n) {
    my $t = $n + 1;
    vecall { $t % ($_ + 1) == 0 } factor($n);
}

my %table;

while (<>) {
    next if /^\h*#/;
    /\S/ or next;
    my $n = (split(' ', $_))[-1];

    $n || next;

    next if $n < 46852073639840281125599;

    is_pseudoprime($n, 2) && next;
    is_smooth($n, 1e4) || next;

    if ($n > ((~0) >> 1)) {
        $n = Math::GMPz->new("$n");
    }

    is_lucas_carmichael($n) || next;
    is_square_free($n)      || next;

    my $key = scalar(factor($n));

    next if ($key < 15);

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

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

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

__END__
a(3)  <= 399
a(4)  <= 8855
a(5)  <= 588455
a(6)  <= 139501439
a(7)  <= 3512071871
a(8)  <= 199195047359
a(9)  <= 14563696180319
a(10) <= 989565001538399
a(11) <= 20576473996736735
a(12) <= 4049149795181043839
a(13) <= 409810997884396741919
a(14) <= 46852073639840281125599
a(15) <= 6414735508880546179805759
a(16) <= 466807799396932243821123839

# Extra bounds:

a(17) <= 220035816845287875103605847199
a(18) <= 8312874692380171296027039757439
a(19) <= 2681395951618532222749348573092479
a(20) <= 2015682772018103721393561366500877119
a(21) <= 318963327603852854703551838867776289599
a(22) <= 96575873711604642053540817013933939517759
a(23) <= 11904606252054573136961965169162054659954559
a(24) <= 1636162251514672000414297492305150276198494159
a(25) <= 3211986164655787981683577018437188107666694635199
a(26) <= 1240595229243924453377171760658386661780374078334079
a(27) <= 193721375771056982300768104636382215438990896474363839
a(28) <= 600565358935470837991354408980747635166784072146363413759
a(29) <= 65822817119168097552045201850004403471114659261121050376959
a(30) <= 529773431881323261469804357578245696950830982491831173837507039
a(31) <= 35538362575499163168318475430745881626873242571951121388412890239
a(32) <= 5183137152005593716792147722696631411275948067302870576463387659999
a(33) <= 475360574280120844167601101847860070430083722011550318801553064070407519
a(34) <= 384997866917764874534466634464726074957515074035536044890674364099007569279
a(35) <= 11405920575436388899601308917841866659856359250449993521589195829434243992799
a(36) <= 1040086557273421983686358821512639927160928136627395362865430481587758869860799
a(37) <= 14577556590670683739920034345247850091983702983314100754624629102281778048226704639
a(38) <= 6078691314550069762784045169468363447411909396582600652921270062309027897007848429119
a(39) <= 2280448260901809987789363426060048497214345166019531051023143520239706374070962193604072399
a(40) <= 80276910340028392492960642051679202930950627236818871376183838862929228673103326008006246479
a(41) <= 1677879201901024688938633505097585449383682501411563061008557286933924629454590950176898086799
a(42) <= 3926081321331300708066167341307821710338325418825136265331874201649903848884999544371273897869599
a(43) <= 10881317600987652917872532362427875386160430491954805180903453975273796285182280390063161902406399
a(44) <= 290066308036199014716980118855055863622218381444281600225103535218902274518068869467076967256770953597599
a(45) <= 96450993029537273001708845147426369398690626975982108276958198434048275661991553984014621357541451141353719519
a(46) <= 3849602052057095622908726233663702024961403460246897807449796755800218801209283699376739862505631630169710596953919
a(47) <= 758960636671784296588850680793435616361120214553055445970655226368870014698626377118327293580120897374152447999
a(48) <= 100834359541792757170828050017775028658532278550335402537038580228030062437910559187180118978260553968493166639999
a(49) <= 511120674175070141430286383405410291207685803748925006240396582618098385590953679524979826271574928031431606319515679
a(50) <= 1476196340145727735310118614150892751662441687908574857344312650518954626730170970564644391303937862913511951029968431693229439
a(51) <= 3790068531955503170848299313751354044900998845713628653216837555768782203363461030623467572471275428648212664032729327075199
a(52) <= 17650686002123428923802735165565633669384951517245150741692953686356402658836419277927788069268168815819538060385610168283346879
a(53) <= 15591506996285442348500495285292722019842233390112181237864206927894646212542083192126984041109618975805718025675631720227732532952393279
a(54) <= 199265161628672581703540163194965337417880205080110203787779574662051361910728686133030523605221331039529645468898304455942293323326559
a(55) <= 41551713253929458396853810020103682389925224061095393933189817794455070460281668417176439549808352059423914509157685244463165346887722559
a(56) <= 8972413400020029662367713471241311650565205329947004776494279537835446032155228711190490606511510159608492325731567272503695986745346090563599
a(57) <= 2954605902787846489865904586142731788803946921506570486727522438552201692089179206417647791200539452120459283333342594015051489008309203677910399
a(58) <= 306533011620976863914442233709852096291157938112841440865613767645261718352289343218915628422659245256377351421826208272946179684087937431360799669048092846002076244479
a(59) <= 152091599375421613107459729038878683715019117529670730588928081666569497207943836851757731933011391269488814710204669386609410806718005415627105479328956174159382399
a(60) <= 88515524129116494917811247368652779806240047832877339806786020191517529515544877384570876322077788971709882578541962587193069701819442989817584884259207159649439
a(61) <= 212453648824107250199795755772652397885110475938023266927523498443374105165468201175908937757567545102185402465159939632387494966617913057647755981898735797869710696613245529199
a(62) <= 630460314805239423092218738420436639870339797130112958128072426496815856566840321521376079445164855118118621833092278644820703884464685150696442985515312071188639
a(63) <= 271499000841899796387088560319622465743951361101708850981184199385292627836250337759755237821014291558456774502499215148045463465348370618007983984187594556578146272945912347839
a(64) <= 922591602887294755184193618575746213552444923237127934938214553062462628072944463154489514646829675368562260049437454492947744233576165530922239570702709453587276591298255759
a(65) <= 821506297627663176218225293034866787177290836060239201590885630391570009975653166050217804008447126527455240288896370555639015760650344761975137036919918623369263749727278603568313123105279
a(66) <= 13175242239836565255824763757880681107204438189462243962023698473570598132412318624347129979048526396122879811687149237287856885884726960961393237338045289092198886651296739447557677691940313778616130728193029110291737119
a(67) <= 969466216083580028367392877735216458589371681292798575943700523750561865685785306052045374427650820199109534506011578097009504115238459613164875327737371670172212408618967246477217633903885572342399
a(68) <= 2960016440139852566353421262278276141947162303442353272995099787050069533488502764445439913133299496234821700181305826448851073595949389967285545166455458504558291299216803089938669225830452442507060559
a(69) <= 40854121493231752429781563327570087974639225026756786164046995656590873732370461183817187536657118461790405132063279792429670341473385038396763601117104612590210716769463822283934611519
a(70) <= 39812751239134996864276184103475492709954786359098157777186131891996799616349311835634154561533811991761533355021701688543085835336916979325210545614230961001348852683823529855001755097099032092196799
a(71) <= 4579580661772960498487212027436502722313027578583235970095773743027834787402138689880953811521059239345053449239361186639720935368760924980632867857273110754440630812062523209143460493814593058077639073061916826477263223567673119
a(72) <= 3937668102129683425261103891752320199101363752110571827552234102865688374902587778125824862064762530976605971802024065324502598394099569609649407774091120535150747459786815641622028484741774124726399
a(73) <= 18116206680070226617920806923106150519464118557882908204217674263473853442117231002583136544337068624446662811503715328008411627736196009736435922676869671040321887961602965179265822985490014613010220019769101055315599
a(74) <= 10224570918616329005046732153423594796986913665361206703004371570625514572369826365949088121048532266792383972734414857198864813370852434931983624207982608390957361342482509078244786742283865999704485003510369283199
a(75) <= 985757605220619042845164366365589025908629104046757603590060511677041494953068917680720453161711354674955769603151321714637818133622550830533363605320745520773566404702625242302226376971272748096330306110800934530851704017110247757439
a(77) <= 6696141547656275390160780719030840812997131610139279205048031047477235519954840494434251411303742455813759630677341395569203260552470989623432967095997658109296420479810065605806748324094678382255102424358097664472316299171873546293815673919
a(78) <= 3446528659092262829953157873447210447793186988925873247035524717685341685152155670879759871508331021792930950570506940057561975899046096080479496181694195482600355415192902687501146419629121380451117245831885519199
a(79) <= 12537201935951218060377301991648206063120634708708911259425266144655681257354561575082170034957320127317605070107730737401208699427538970816301866054900141020651569769051109956076394732714036682013937975962206135730639196538937420999412322959999
a(80) <= 628040288081671207024491059805252276785918693284172780656735199794553829628321896980706173395549664985270276103095542278488241359301131819929500205250019042276974689727544414646909010264373433449511948569994505256548731903621630335012775437849855537885199
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(90) <= 3061339237235340559968256778766376368557210521236822683241359539086756393937657077266543565841607231608162506022987036201159822029532608803464375351731075740297074487480457838008065114202077908341965189216535110228486343600141904557675857477487155663688692406503313518373599
a(91) <= 16171782685784799960288706609559206064561349098982272842248649103888502411942417221034490083331599570421612265341681621905639726810704160255665744752635527800967894794344165114025035652253255399063749818113186748588194156986408165087483148644054350262710491244185505441599492162965130675583475199
a(93) <= 3406141975535689816407935069185696241790557133216001676175874219592256052677598633472088727218487967139275079700792087213409876917514779375770257283551973662335969732153087444878529963153671209438910324105694878318710565211142848392021849691618584614047299960041061426532671269871508386502231199
a(95) <= 10207694831684141978527808566224680049088521333707660469152963500092147866293433680133322916219470123075995388619813996431413871126094660669963138582420244029639560572346366971676823464818600215358501457097527560560978051313877214005268541820381693839789140202202959875187948191058192297603873657141451656671830146399
a(97) <= 143721179913091569106846164030461708672131513600111690352143931734313843502898465521678428028153611375700651513269693593824251540276612137957555951719036432727547813120102879578982289672653851863231655458496356076706738257343841482191241882871876489921505621578677123809894488922438876600360599160663231705732652661379780799
a(99) <= 653625089448363119392316763306860428318105878826522620571005822295337710281464589836673463478169351857530152733727369572798827376140987967539931368654055456760612955570318432659217959696213945791370285792018956279174247015719626209098248614116808883427095314443167288950160552115752114397246486578525575341090261327940409022996883044799
a(103) <= 232295314706109054050525303457645296943909553186195224705322344977868403916097937615231989970712724952106885796591789266791044434076351197259636355730790851059896165852424404727075372892358816227316709466052841521385166162196375516006793132864586589968311501810549280492295950029785211158334604304545437075071891514576729011502222288799759
a(105) <= 22154722255820002663559983903166335966016049236569789316063909711055504425573887461699364549708499091895439401927856842950260001515149001304947146271147242135092595035768907424058028281247907072752926671390429423752700421785423507769233224046700876991388323618717652596904356254986041957725291753061380702709945381290521540791863265689075184319
a(107) <= 2305798397332324643882687942876065691091416495768038202828301957984572131609696709285185037876425459103858532285286224498810691114321258329323592678145427000520874025492522502456997171954792336414224472686146231226771962863289611865982827797162430473257868840101751386161372443243090095877145715923247976950499538799922634464167417430691271455959319554799
a(116) <= 2937262310531690240977869173784388542022922357713361261496002762588423028436601182904212844529389901813682136043559766165926126865660138296102358377143339661199646023830669332699939731657989310893734285507054879149255314423121718787000372073799733366762098782909054579430720137378485222516374779972553986165509004099190007977345593295496299292297437466806424421692743155630369168881470122102223839
a(125) <= 2198262252097160628431744547105000874793047500677488027546376936203287235268126647906971678119505297872355942427211069228999513114107815850301664980029987677545671399316481771744117645937176295440068330445148203893310615817596215966190206070226628651013059973901557161632874424112903887830095292651987186339693209231862796077371365337706494946103414122272949984636565788125827319341121540719731838342747614731199
a(280) <= 417087935487143074010759494913665830869258942901267926396306277016880706436703489453249816207609861026061397306366792839474341175425130543145678096793314412758791827469178935236441808106718151771293778222140548543942801653972602644189305043290435208271680056525478628177625284766335096216726632802012880177466422259049799077851652730630398467029222083224540198532999024181874950360998874121604195674834159907946126731146304106493297895436227833115698101332309321963382636207017639709631243597732409259128460715317033948241950384865199246617176074448833213847605235831759624610015076363469984107057986027811765793414147445078671027923003805083349807686317855646596896112414314757429024901063282869367759459052944054857164978097392466771232554226955814504047727654424862999163338687326061055637433565436760884575404728978750727355545062053911892623493829027850908282401945051511970412239258174665372242157779113394858498361022069722785871113249231725845204741433022568464125635468506012126942690859527942285748567753486931118217145474813019602098018466105437764594252482193726455698151252155491892224938425585119620296121209255213563080418342469295452939649591693756651765660910124683999135679696446044565566039505599