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

#!/usr/bin/perl

# Lucas-Carmichael numbers with large Lehmar index: (n-1) / phi(n).

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

use Storable;
use POSIX qw(ULONG_MAX);

use Math::GMPz;
use Math::GMPq;
use Math::MPFR;

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);

#<<<
#~ sub my_euler_phi ($factors) {    # assumes n is squarefree
    #~ Math::GMPz->new(
              #~ Math::Prime::Util::GMP::vecprod(map { ($_ < ~0) ? ($_ - 1) : Math::Prime::Util::GMP::subint($_, 1) } @$factors));
#~ }
#>>>

sub my_euler_phi ($factors) {    # assumes n is squarefree

    state $t = Math::GMPz::Rmpz_init();
    state $u = Math::GMPz::Rmpz_init();

    Math::GMPz::Rmpz_set_ui($t, 1);

    foreach my $p (@$factors) {
        if ($p < ULONG_MAX) {
            Math::GMPz::Rmpz_mul_ui($t, $t, $p - 1);
        }
        else {
            Math::GMPz::Rmpz_set_str($u, $p, 10);
            Math::GMPz::Rmpz_sub_ui($u, $u, 1);
            Math::GMPz::Rmpz_mul($t, $t, $u);
        }
    }

    return $t;
}

my $q = Math::GMPq->new(0);
my $f = Math::MPFR->new(0);

my @results;

while (my ($key, $value) = each %$lucas_carmichael) {

    my @factors = split(' ', $value);

    scalar(@factors) >= 9 or next;

    #$factors[-1] < ~0 or next;

    my $phi = my_euler_phi(\@factors);

    Math::GMPq::Rmpq_set_str($q, Math::Prime::Util::GMP::subint($key, 1), 10);
    Math::GMPq::Rmpq_set_den($q, $phi);
    Math::GMPq::Rmpq_canonicalize($q);

    if (Math::GMPq::Rmpq_integer_p($q)) {
        die "Found counter-example: $key";
    }

    Math::MPFR::Rmpfr_set_q($f, $q, 0);

    #if (Math::MPFR::Rmpfr_cmp_d($f, 2) > 0) {
    if (Math::MPFR::Rmpfr_cmp_d($f, 2.15) > 0) {
        push @results, [Math::MPFR::Rmpfr_get_d($f, 0), $key];
    }
}

@results = sort { ($a->[0] <=> $b->[0]) || (length($a->[1]) <=> length($b->[1])) || ($a->[1] cmp $b->[1]) } @results;

foreach my $r (@results) {
    printf("%.4f Lehmer index: %s\n", $r->[0], $r->[1]);
}

__END__

# Lucas-Carmichael numbers with Lehmer index greater than 2.15:

2.1503 Lehmer index: 5232962575890838242345559222106375262945427036820382084564745931115089865281183788415
2.1508 Lehmer index: 151759149709402024363800763626585108964371416663774195956290091543901518037262207815118285358562835307112478044154801451026001344290802069118788718949749367976404978038516742605026815
2.1511 Lehmer index: 844652921623815779584621666312020618539997410827718241495641456058694006372959365185808341855583942978096255
2.1522 Lehmer index: 1170481105185134958035023421840712139755687198404981653849462347603312008042936364224255
2.1530 Lehmer index: 3899907010715937933083922000047475735497858027157964195609144825174322748358547956958703064105167978371136375360740309726921530769297946021011912847877092335457215
2.1533 Lehmer index: 384380986755692502658654887312422864906849423194872101672993621671022188451286227801464023497073360778264997792255
2.1535 Lehmer index: 12842840413387450039118922094150507198373150341080498833706488673768451737215
2.1535 Lehmer index: 4511594279503034706893673651426767021146324183522862431231967682171474886121626696134509752944861695
2.1536 Lehmer index: 69337381471465462540705123852382693937277972329781289176585309862320819037843893263798584705365894864895
2.1543 Lehmer index: 13057477553646473166045199720747254109624032607126145269755459901885658820532088485166009942785535
2.1543 Lehmer index: 1703562561008845877765343686626576341256506878588397006257696367609575597143362047070437977735484817434619668681582796952466131655306758870655
2.1543 Lehmer index: 410145027757289355528803254869478003464399194685778494874071353450773357232318476771769267703935
2.1545 Lehmer index: 2665722552323527963501725437894683314807987366090764825815474591490513280667706921708889023679855223295
2.1545 Lehmer index: 56337620996650020793753998310221127275460951292913265377924231323569159330718863943326643510365923389743447759895576256063391280186954397695
2.1552 Lehmer index: 3222468409034002575243088308108035097204956783433489668426893515868074791322185165970278553523420025494655
2.1558 Lehmer index: 4724694174037479296753843910876131404659791675917746217445763512252173168602116801957247693601312631260415
2.1559 Lehmer index: 26464705204720235395243648949100283216860608103271961140831052191052184510222668820666797523746032525650520994019286444415
2.1560 Lehmer index: 67061396395588821319225271874940577335455664498917672780285983764926978324925757427079964501399009875114926235588045016159991131544978507959216906893594414126600510217840686549223590655
2.1563 Lehmer index: 13384352475103291203873559116020400511621353670941875363055889902299256736073039216550560728617943295
2.1566 Lehmer index: 3255722421295073230229988297525524203395582779804406251136633771212815449504783252279054726917546632922718874096300867273535
2.1576 Lehmer index: 2133027369308339914887151222278592788239283606062762089172290311091725976619383045082663779171706705514573788493844988152701519156628519451906118725241642820120250459013660228883843219983047625098773687290914568222496713421801398506495
2.1579 Lehmer index: 156745563690452859434736308333702048628972739220130356544159614093806118670187597456719079422963598701220030079987137062856387226495
2.1579 Lehmer index: 2639998728226905725115350331366399552110518127525284817708526335
2.1579 Lehmer index: 21908844010879513998070777158083921861234673623356430451580361233438752866680335462220489439615
2.1591 Lehmer index: 53138398094717523936628958278903014203910886243265312312352630104306046730875664050440300265734015
2.1591 Lehmer index: 46772477339896303279907040130976586611677225923237639078585512559436367063329551941158597397949695
2.1592 Lehmer index: 6105691116467257437724035553736682784890670593866710488014294719469994658874578107072661983845542560867155707902249215
2.1601 Lehmer index: 48343220721794141760482074787253883666555983937931463209773414092342727976689205338030678552745575355499293960560825863024174335
2.1607 Lehmer index: 102515679510036678582402832291082711302504692559830711726735158342347027758732219211077330042345215
2.1608 Lehmer index: 2831623897693324664829966381875072570179785572676310172565215180708308792696691821198205179179798201117111878015
2.1613 Lehmer index: 11282417722192795208016694995967275216735000173535017486110856310328718995028769767158995337524695060951021557784091273215
2.1616 Lehmer index: 24310698014160010310749313013068622919013802712267027259077787135
2.1617 Lehmer index: 7867636824745838223409263332702710040998969039523782219259934853448081916582574249402111829749089865214853217039621860459391877507960462885988653305782317750324735
2.1622 Lehmer index: 143026258951147983373291738720989009749382987168654864692439307734087171278122374979755283014872372914997165577364358712763565860211861199914625020937839088051186444159855415535544888578647235504822051093393442141186582586875451076940665177855
2.1622 Lehmer index: 87412105447303322943520071171812427273317412752287026028359404466891615414690106606475370806372699996557380647472178655748037144682400047809535
2.1627 Lehmer index: 7514588523201404866020504066290388077409838660010553191059282470362039041772159589770138495
2.1629 Lehmer index: 1539778989805453931704605369559455185667979868859276742000618377746470308746404917983541607498991295031629796660626063785656982468647256818236475943459738151778865530920470015
2.1635 Lehmer index: 708080286040276247573286941132496454792845945227519230454772138306364190797749566971480367828250926380825710177519370626970837428019203359615
2.1637 Lehmer index: 237782614965505765652388454391107081322923408716826394289483123293198561538881475627935642407850808058984976200132206676136969450491217966920720734729849215
2.1651 Lehmer index: 4243956145856691488649853257507752819688291234668900526510245226244046303029023140365005594780869266038877254779170094433214125500034880034788337143123466118709589433100759366733846879733583731659951615
2.1661 Lehmer index: 7503803011401945390313632567155889317779849241720023200027377912291874770675496211600534991823238932817662007679615
2.1676 Lehmer index: 1052449257995808516558772060796508547564702317190237996448835400978907896322445314841067306780415
2.1698 Lehmer index: 377080535536276592253796423176443032560980777230031484946338188720056863782039214209739994210096581248220715568530843942655
2.1703 Lehmer index: 43825803010805233016544082034170578092422643088780601042660448508280269372251507615859531178468504974683716187916880294943395647298723610076531184486834546019684360060759169508052443004142751627078744327898523272155117785465601535
2.1705 Lehmer index: 71170318191681802908201833464802802569007083683469926541097483005021352441781809048362095475301157532447789502621780642082564311963798767545977494302795743341193478655
2.1708 Lehmer index: 17933607380776953547401494506279782365552194507785521942884591097730529322356275937515746759628772146765603557839325724254335476932420638490668415
2.1713 Lehmer index: 1012591408428327888883952080728349448745451794025524955777432246705535
2.1714 Lehmer index: 115485452918780711151142429848020531057643025526618096144101358834408451288758160843098511117297067549979649552172961672257346135984598966006092805213232501970407871769382633756531802495
2.1714 Lehmer index: 3525640083071359426950533598254613122919896092061877251620590307879239602990387932743281143295
2.1730 Lehmer index: 128442365531799064156139510576495802513612486529333847930761533581974291983374969725354207967087368374177434310907963276692898670021010491481656390714055478242018340424490294608743427277513498508995462541550370517316566679757695
2.1733 Lehmer index: 49093820569242497421539735961631215470145358790391203917681900937535026291790026661017013155301909736845388732080374143102912127113685479415926049857094468330973122146382877905568276561233378906017140098983924720938104860386708196203616895
2.1742 Lehmer index: 30936167096013568339773976047978340648756206742106115494596280619371357021828349849897704669900915935892729686111634980705476018793593906185914516587044915289319632401970797232705212736811698133366655
2.1749 Lehmer index: 317563585230674118003618828350830251555421989549256372758646335221098241354334813230269344017811664302335
2.1754 Lehmer index: 62204465720172726607845388078220007465731660555634304575600763947402648711114238381352103610031921939045731363333517882021981105579879055491810647749043815412290384749372112070655
2.1755 Lehmer index: 2136121975454165611873039026801263844635407890196626321436053620072639603163682986522017275442767284155330641168457219432918630844733426447357701507094694488736790222335
2.1757 Lehmer index: 372744321825508917589825780622269559207106151696761261456904829356364259901485259336473661995305966297639832265284800660006690320546498396301028774198385455766099865816051904623385725836354290482015615
2.1770 Lehmer index: 38269837134780176955108451814138295025392216034979454453555346572879900055568806315893941105962562908131723112113415782793006630655
2.1788 Lehmer index: 307322174499281982330271601186634282113080388101792969637125665253165770768035314406511873589376099654234495
2.1801 Lehmer index: 60269674625477722588328759178306405054241442923209669607306532903478729504955756682565401469600942373139641181375332064438580532445894065443349509778322147208887582864167834007258495
2.1806 Lehmer index: 27464378274128006514345068856535084247383796725617659211180883163979692012912796031841215269154793788548943432008945524745140822314236490983182185325143961465855
2.1807 Lehmer index: 2942025530897847303059161553127696713836422631991047280018992141639957231266992782899028741338169414312509581365432910371840336199601153489104075471660329480470470729156665358667312099455
2.1833 Lehmer index: 1252458644660264955837817577779489039780648512945893109814633472020085149868079698531417855
2.1835 Lehmer index: 145341839823538118589908940737089008244918217600245448152926415496883873367510744550924915919997615431767890445581676616890202279831691259121047263902991465683564018891177610818644889492095
2.1837 Lehmer index: 7005574242102373354265832619421591501498581348426752216767036248226680037401546168161301314227636581438008139433458859307805227873100196476026293677677879531759791319113801558809031601549479001610956397055
2.1839 Lehmer index: 67036499387324497796155974605642471716635418200373323301576807225369370315312232029559032523487129671535586297421756953713123091684013481812885284843941358374196021224408282294478213444661587221100918015
2.1842 Lehmer index: 1468886623107594191985089259487454023529927338735335871572144088372126718224237406387346265930975252826018335276025855
2.1843 Lehmer index: 1694262560759953154526670348772907540796170513663501032910914159595638310756094357081473065962067590116463265237063341299898280745740931429151682087763596885768443007124275790061776060783308671770836665700299939287935
2.1861 Lehmer index: 2594145124305120505650019954091626919606128354602761434556536080738401442000096118992495759705889535
2.1865 Lehmer index: 48004480252852051285646070549127157890047486834077474187570451588852311338015732768562351620886252940556400392906811824917925622572444790546815
2.1894 Lehmer index: 787222305052394997724945516547365754011662300885413176469622073745477582640035495534105574008781335434719275080742355938058765385165632993837533689399387050916367220851560972415
2.1912 Lehmer index: 1120416428168792738913288328714108075486596731609500545277404161754024902457216989103636273073839624409271473732654088529349478546697842940188727574450221416527231767306447775225485495497262801144338725957373407467404701055
2.1927 Lehmer index: 460904006056686426887303849334911434365320374753443778612928069139740807299223897362251200121979223985201992131540581322922430436263834889072617722535515257096631290414859505532710437375649860660512051091130670806208295840255