smallest_carmichael_with_n_factors.pl

#!/usr/bin/perl

# Least Carmichael number with n prime factors.
# https://oeis.org/A006931

use 5.020;
use strict;
use warnings;

use ntheory qw(:all);
use Math::GMPz;
use Math::AnyNum qw(is_smooth);
use Math::Prime::Util::GMP;
use experimental qw(signatures);

my %table;

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

    $n || next;

    #next if $n < ~0;
    #next if length($n) >= 35;

    Math::Prime::Util::GMP::is_pseudoprime($n, 2) || next;
    $n = Math::GMPz::Rmpz_init_set_str($n, 10);
    is_smooth($n, 1e4)                        || next;
    Math::Prime::Util::GMP::is_carmichael($n) || next;

    #say "Testing: $n";

    my @factors = Math::Prime::Util::GMP::factor($n);
    my $count   = scalar(@factors);

    # next if ($count < 7);

    if (exists $table{$count}) {
        next if ($table{$count} < $n);
    }

    $table{$count} = $n;
    printf("a(%2d) <= %s\n", $count, $n);
}

say "\nFinal results:";

foreach my $k (sort { $a <=> $b } keys %table) {
    printf("a(%2d) <= %s\n", $k, $table{$k});
}

__END__
a( 3) <= 561
a( 4) <= 41041
a( 5) <= 825265
a( 6) <= 321197185
a( 7) <= 5394826801
a( 8) <= 232250619601
a( 9) <= 9746347772161
a(10) <= 1436697831295441
a(11) <= 60977817398996785
a(12) <= 7156857700403137441
a(13) <= 1791562810662585767521
a(14) <= 87674969936234821377601
a(15) <= 6553130926752006031481761
a(16) <= 1590231231043178376951698401
a(17) <= 35237869211718889547310642241
a(18) <= 32809426840359564991177172754241
a(19) <= 2810864562635368426005268142616001
a(20) <= 349407515342287435050603204719587201
a(21) <= 125861887849639969847638681038680787361
a(22) <= 12758106140074522771498516740500829830401
a(23) <= 2333379336546216408131111533710540349903201
a(24) <= 294571791067375389885907239089503408618560001
a(25) <= 130912961974316767723865201454187955056178415601
a(26) <= 13513093081489380840188651246675032067011140079201
a(27) <= 7482895937713262392883306949172917048928068129206401
a(28) <= 1320340354477450170682291329830138947225695029536281601
a(29) <= 379382381447399527322618466130154668512652910714224209601
a(30) <= 70416887142533176417390411931483993124120785701395296424001
a(31) <= 2884167509593581480205474627684686008624483147814647841436801
a(32) <= 4754868377601046732119933839981363081972014948522510826417784001
a(33) <= 1334733877147062382486934807105197899496002201113849920496510541601
a(34) <= 260849323075371835669784094383812120359260783810157225730623388382401
a(35) <= 112505380450296606970338459629988782604252033209350010888227147338120001
a(36) <= 172830055680118494946407003033666507461304818401153193809383963715892256751681
a(37) <= 804470457257926449746758080269993968890016257754008080494336091899208072210478721
a(38) <= 244899124403114685817402147257255073631462537923865013235929258099059306044154477281
a(39) <= 2912560918714425750692738781370955872381272347556033831319694306259522835520469570883201
a(40) <= 762210196326887044325367248966380975902760701181511152234450396289280966119042326373721601
a(41) <= 52485123286134326408263823591481242377488247689573560439506054269103209176125566751639312793601
a(42) <= 11712949958722103183860743398189942384559924300550864434051075391896219527153519139257993442241
a(43) <= 62039074630871680786441646919621192229792798445308789548113238024230574070735729799978450334183361
a(44) <= 23959741060004084329390586599745164525018989635095789558070587545425355466596976334624539288424681963521
a(45) <= 12591840289637800666032149271000155693270546180687498101807927335145013721437719355117946830191733351283361
a(46) <= 15809529585215385019753212431031270723885479914879305809455110220044605125473213278939340791963069813678322001
a(47) <= 207270474145557124383979968634792228079586178870396928987904448897248653443245526549895600817320240588922003601
a(48) <= 29012671796343960596676352324317520715530460877423381517474876615804169174099100363452369698553141095314599703436801
a(49) <= 2623442501195679768267115874819569192451318089974584721342844296892907865692726956503685779657184079435889196419832321
a(50) <= 3720760251670931086148518598170349751587040656178493663334872101126811356479706682192087192676906294698316800009914281281
a(51) <= 418417201875159064198354497105079548236405459277898718717711834828748770586823595475058067498254485016320587447571659138788801
a(52) <= 1054249285425462908322766041550136398157336757411012663632000621467301997135693062836892278515948685622243725974152164457352001
a(53) <= 6599208217528062396767749189078194725715868834371991595801720666908141068589468527316026247677672688470577846891786597602731174401
a(54) <= 5982507945790758432103197898476966005691803021948156243711546789590667101380014972310392651274761901222289633240313417865378850029259201
a(55) <= 13386454858623727749849241483400378279441176587014329578479095847657497277050591853651181361105530315604274874898486761301743053183351579521
a(56) <= 11164687339374823139987952050568240830555453233215503265882245671169470870505188012893156810304973942228644839431669660517855895066055585956801
a(57) <= 8102746826725699718379756989601894928284821047368913522631597796107975385296135949022215882032795926196038858184547698017628828754626881746845761
a(58) <= 3133161974370849854229875025601307032723202741595025644782936526319134902165376510894436270474091459136871854282058674714222043241333733752803786561
a(59) <= 108145238190989474973703334283474625023753010519732066881268465037843805471434566167336720204559485435856913507914821012201002144190397289199135481344961
a(60) <= 32130588083650713548419239478903259185562547237236947716533557389243347042900998620124002629627834096730528094842516759462343839281941026140949043376170561
a(61) <= 2425780991022732369210226442205351936002787613492557680438034717804083726018096625364638299142982686883124324493080003983525414032338636848719379794825804001
a(62) <= 412840703411014164528528619730286115136124032576693518083630303414953073765607569738235052327435891059350027838102426343178107608091720075884658274052290775363556401
a(63) <= 43408375860916010912641505336429867345339819700966913227321441774838543422649307040173334118328617020199451073751354541365930390020282027043508198383748659772448001
a(64) <= 884698557582490472317671587927234095030114127983917458617155270745967933219119512078582987215090504727997329344588475608657006974343428059188134966492491138451144801201
a(66) <= 606241555364969266182895988110298608667814823619173311550415404146218396002531233005895844351567259872782892694802666928882589706026001913163779896886445989912009951941805200961
a(67) <= 2095356876227567314474980358051510021507321627692417613263104425940914846046018450882183080803185866479042339294708881664021761391743533513597574006460435681729345952352865472877281
a(68) <= 19809143112372317957196706446239420230701846060478812266927089627942445127387538225244568755269684350553948311247611317333708809258782549719674416824359383509403328586251053695591784961
a(69) <= 35835413235325168202332836142781552872014729913026655588612162555090954108949839011282795611460171343099422919657716418638966880099791821180794371217808373460237352410747167407346037346401
a(70) <= 4222613956813640651492407552560372051838776351498818923191289951761513776992247080673647085462109511840554058526026346356065994547611681205155691691004168767467980134007379572679689777362364801
a(75) <= 743018326444327653222145267127575714961144040047694871617424755291355624266155669327751196755712880377180603658667471159373314546057174323698604890095167170951820132234768226855677369766868800228717060166081
a(85) <= 935008228039333137382223424193072790312059389375709005574656872726473596696909837631757440904508279604664321446243625038770324552353934906403158053574735433301702647306851154951465188744996990913082212053923207619895014006261682701794401