giuga_conjecture.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 ntheory qw(:all);
use Math::GMPz;
use experimental qw(signatures);
use Math::Prime::Util::GMP;
use Math::AnyNum qw(is_smooth);

my %seen;

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

    $n || next;

    is_pseudoprime($n, 2) || next;
    is_smooth($n, 3e6)    || next;

    Math::Prime::Util::GMP::is_carmichael($n) || next;
    $n = Math::GMPz->new("$n");

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

    my $k = scalar grep {
        my $t = $n - $_;
        ($t % $_ == 0) and ($t % ($_ - 1) == 0) and ($t % ((Math::GMPz::Rmpz_init_set_ui($_) * $_) * ($_ - 1)) == 0);
    } @factors;

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

        if ($k >= 5) {
            say "$n with $k such primes";
        }
        else {
            say $n;
        }
    }
}

__END__
182236335107905
8900440266335905
12535997755121281
32694109868534401
99607296796722001
247669889070641401
508355622502573105
948176051223227905
1035715429429000321
1309484904736806721
1536662633048500321
2788095177623795221
2800325363436201601
3906953651494908001
5925843848972505601
5934096503025054001
11043400180257768961
11075970438654408001
11290755205951021801
11442270997310378401
13184441559053251201
16335643957325519905
18211286556336154177

# Extra terms

20924832851653904820361
164079759299511657026970065798058008305
9818231751330472765505103642827387462365716993411973684145309281
2573641097029495387492597584144118325201548997854141724937057684959345761
27074429976830323825190236209610924364684591729611163238655750811422839206641
1178160667498440302097008801954701760350890331375708111605104372022864672224691667481188801
83640408502949929570946635512393569168169541179751917159496828419944902520439711512486083992001
144488126427660693953536041463592336371530955223034622604903955706697775585870597424500383156376961
239912096549901911658143542428096880869707349198379203276133584643742188379142764105673110886955573095619358401
781604832004927870072158550879811405545405641425760476798261179926894049356319247618586884144841098559980119681
25850913339504270134208764730159667951829918448598666884307156786341279201532189149912557999276501190371674895258205077878891201
213422115942340043369820231337822275691121826480419559657020690964571827740302624147800380811027478135188688916699637730683102887980468471816271476801
493406121674846876320825042569125570984195009559150542241640731711906005581852340942286799679638448630779855996192751047592931735376013647289704266922764165821426856184843097109282054164420121699111457012506448215370718349238824211490881