123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215 |
- #!/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
|