giuga_conjecture_cached.pl

#!/usr/bin/perl

# Try to find near counter-examples to Giuga's conjecture.

# The counter-example must be a Carmichael number n, satisfying:
#   (p^2 * (p−1)) | n−p for all p|n

# Carmichael numbers m that have at least 4 prime factors p such that p^2*(p-1) | (m-p).

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 $table         = retrieve($storable_file);

my @results;

my $n = Math::GMPz::Rmpz_init();
my $p = Math::GMPz::Rmpz_init();
my $t = Math::GMPz::Rmpz_init();

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

    Math::GMPz::Rmpz_set_str($n, $key, 10);

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

    my $k = scalar grep {

        Math::GMPz::Rmpz_set_str($p, $_, 10);
        Math::GMPz::Rmpz_sub($t, $n, $p);

        Math::GMPz::Rmpz_divisible_p($t, $p)
          and Math::GMPz::Rmpz_divisible_p($t, $p - 1)
          and Math::GMPz::Rmpz_divisible_p($t, ($p * $p) * ($p - 1));
    } @factors;

    if ($k >= 3) {

        if ($k == scalar(@factors)) {
            die "Found a counter-example to Giuga's conjecture: $n\n";
        }

        if ($k >= 4) {
            push @results, [$k, $key];
        }
    }
}

@results = map  { [$_->[0], Math::GMPz->new($_->[1])] } @results;
@results = sort { $a->[1] <=> $b->[1] } @results;

foreach my $r (@results) {
    say "$r->[0]: $r->[1]";
}

__END__

# Large terms:

4: 62307701066505659401
4: 224743092663563632081
4: 251954207405048635201
4: 518419682953950420721
4: 14079283768153363400641
4: 20924832851653904820361
4: 21554461999198620979201
4: 23303532006976361263201
4: 47098976945256401443201
4: 100673630983865246068801
4: 133242578226325247803201
4: 292738793474965453943041
4: 350867089701919756643041
4: 553796163242951913174241
4: 666954890168830933461121
4: 1287277785712674618280705
4: 2922686811907334213783041
4: 4358368080370761589813681
4: 5979814320838736588112001
4: 6522559270725999063991681
4: 9172056301025491069338241
4: 9803088748605222164571841
4: 16668441789045904927072081
4: 18794550676788553204390321
4: 41371734983313344434531201
4: 56619381943846708386559201
4: 63531531968436807857505001
4: 94919467757903738041579201
4: 116979925928504957814459601
4: 161248852070795597957085601
4: 217382074785847138391904961
4: 314110055344936020132902401
4: 488990398526860474994873761
4: 2103354749932168459920012001
4: 3835170215218636259167556641
4: 4862632272169454125452396001
4: 5643528331620848934452632705
4: 7862937874378726759817964481
4: 15811568876773291347113154481
4: 26530971207930900025633735201
4: 185613531054132621117656135521
4: 237407278564013762626171344001
4: 320897832354428205152593628641
4: 389360548694843929399001400001
4: 396756459116792979940186074001
4: 459308951541653752430375047201
4: 3383926409253443636340952755121
4: 8674725844670375736931246168321
4: 10506381424017524148237200852401
4: 16895420116599694303827350318161
4: 24679166739279035112307365233761
4: 25900516782777980409633672169681
4: 39949222849052847860058132290401
4: 40681933539482761851736943703361
4: 170038140478707646761283367521921
4: 184322280051408794274145760680801
4: 256777028538201231661213022299681
4: 307233028827572558435913376434961
4: 403422910766003900411436971260801
4: 1460192971890848891832572271368401
4: 4813466280947524669348816329926401
4: 40576966219522737898431889174110001
4: 304427607756494132682383579447326561
4: 599992042341107866310065015772149441
4: 869191344300603484347195168165692401
4: 879604250913524369200191751166921281
4: 996321080683955306033734480662753361
4: 5067797454758535300447458806417613041
4: 12001229251128464794651576334957561281
4: 46340091253351698583517514518357030401
4: 135930643232730751774724025675074797441
4: 164079759299511657026970065798058008305
4: 285751589832023654045542269805215768001
4: 686462464005648105509066286622678406761
4: 693894183838688572023676620093597532801
4: 1347711273699039935088839415467102341441
4: 1529824644929077481767876452013913685505
4: 6567931672880046783499256462011663056001
4: 7832937744374326274460438348235057545121
4: 8710976207287364861319139654975259231041
4: 15696812566198628284484523031394232700801
4: 46630547225797939353236016285659754537601
4: 66430004914349671329838564537063379515201
4: 97844598178382813522843275940733277407121
4: 130309077211927607445366398115672812494801
4: 203048665828917850457076419929413344826721
4: 276382366592265744685577091954747039418561
4: 1916411281725867816635785673902755049318561
4: 3097581662176314907890466875533900445595585
4: 5174523040779267813316294140085358395389121
4: 45144762055023899455093329906790228567121281
4: 50383052584513396623604437609061853950381201
4: 52631009899017059987302871302752535785748081
4: 201755893199577268587217283830714437723012001
4: 3157381069085925270114000409391702939929922401
4: 26369706525016521275356890196326539229573341809
4: 184948360508526598828521889125240665841474787201
4: 718558753437710438956320887230919792621228966161
4: 15845616235571778746477478018463391498230610063041
4: 38070284731408037766410123298262095602533622817601
4: 42222165298274550028721856436467945084344356961281
4: 55121737760578958460561108050903301487831309742401
5: 80901444283066458657474733731432417706450446952465
4: 187789252073445519209787690506496296460371927245487281
5: 944627055894286384877927287033256715967293493012644001
5: 139472232694052209475326651140676807442188455542142613441
4: 11927175584522213302001776367636111148214655359521403466305
4: 9818231751330472765505103642827387462365716993411973684145309281
4: 26185541602202154197967798917212494747497829240013558226233056001
4: 17166200614270345782630192325609887512732520159539392702847799892561
4: 3107688073496349706409955340086926364198660458861455909166086215185665
4: 2573641097029495387492597584144118325201548997854141724937057684959345761
6: 2653521458315707381053683135589765593289443595621000711556334547063203472481
4: 27074429976830323825190236209610924364684591729611163238655750811422839206641
4: 149500921027080981282124074729176394565804677969550057557348911573406305835803314606801
4: 311166300983807801937978239972747615382721122699056223633309693167440315213063241651905
4: 13283275167706917959228898755066314711304647190087932179987510690609737081784453481764961
4: 630680938429826741362869501216063336131005126396478362876178071553741580565593761783594305
4: 1178160667498440302097008801954701760350890331375708111605104372022864672224691667481188801
4: 83640408502949929570946635512393569168169541179751917159496828419944902520439711512486083992001
4: 39365515140134937275377126113363723953863762672143899256470244855471018239660732337228714840520705
4: 144488126427660693953536041463592336371530955223034622604903955706697775585870597424500383156376961
4: 108330296756607263150091769685898107659238710444044423123268292491626168698243127585887853829955164801
4: 228084324692688249411058086354639432493913679802617605850133666674341551882439562767287112806978939157505
4: 239912096549901911658143542428096880869707349198379203276133584643742188379142764105673110886955573095619358401
4: 781604832004927870072158550879811405545405641425760476798261179926894049356319247618586884144841098559980119681
4: 866113392922249443109253136057541328722427788749780221245709036143091075650715652529167614015013244128749363374081
4: 8713792660623440104628825477587012834175156112293202724282649545679385421567179010428426871236168165343941465494401
4: 25850913339504270134208764730159667951829918448598666884307156786341279201532189149912557999276501190371674895258205077878891201
4: 596587357756741395427578802912304959577948357653358401821711375085458864395398130445909766569877553822716148796454099521885250305
4: 18322921296961188436685266731373086340639254549820268216140399345500402255146306763256794727782432769806291517600115936909741045985886064401
4: 109063520702072024241354171023277751994787275338588482843700490486801130933339434867109268691751064339204332032543783403236151032084061607201
6: 2735315496859458707504438610847263011629873580929231072103290440200856302803350709113674964052140350481170753127138142551862327899692574404535121
4: 1745866852115383674141641834624495814522743936401749981466180677282850328312620413869511030554736217588065616789659361606641228526395359567830750801
4: 32033507255810781872096792529434713132026926635761158376235056417274134584523683628989466209658948872572112242126420262704614991738843607644407992401
4: 213422115942340043369820231337822275691121826480419559657020690964571827740302624147800380811027478135188688916699637730683102887980468471816271476801
4: 132543823230995422216907088342065347656370442096059813127463509705208582512405050914411342638009066346803161273579766097493429745195376853063506842866801
5: 40184457922275207788090353549472301408131369000526958974412327846947492325305674006965868166061402041356872891718253920205922722124688294029555221579688801
4: 1116889181921892253891515764232859408587235490356548035904627064391291611910635607888983093603912745156334885954735806517777509134642971159386676081232779505
4: 2182640369359529214638830672842393189603795878844708769311544505290782335952410407043172029951798968429162282430311258004710982485783282789992597812502830801281
4: 993105492311067415417479462041707500107819924829957607564386671276253417114814499204161162636319936640953931140578199414755646183262953352973567819636316060906748001
4: 495995603269835954872994379496572152801663840951748696334955729462911034612292282842583468991911705216084695448234341423689717365439017800892682021948727259414122199470482561
4: 2552522456492083309333165101575452907762982281145942391118525339944134218339661060240998121678909203490966325758405820365266390648488128297062115064934656446931378809287376001
4: 691144222100048164677760739498971255186722624539112865349589760294480075672544412990260714281543611928373673090282940295652582117003705222135582331726538857199508545630847828184541718955660801
4: 9414581673293425275718963389668786831584918112296643365462837063721096973565130924891042191718752831894654360455675912232406002918312213432832442547060756528699711856984149870331844472878138284108689084801
4: 493406121674846876320825042569125570984195009559150542241640731711906005581852340942286799679638448630779855996192751047592931735376013647289704266922764165821426856184843097109282054164420121699111457012506448215370718349238824211490881
4: 213218398511695638101987881170547303776997720763935745430792190756354877212978865297495989609558331777539589279597119051368279501936314363865675203834308314035689460935227710775452917877647010041515137824334977223449697624910690221423164263213273412372815947281684834572585890737333324080672320259173483428120850855545963962869640130393331380140226065042883836491853202710966755174469625950721