experimental-projects/pseudoprimes/programs/carmichael_multiples_of_cyclic_numbers_upper-bounds_cached.pl

#!/usr/bin/perl

# Try to find smaller upper-bounds for some terms in given in [1].

# [1] http://www.numericana.com/data/crump.htm

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

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

my $carmichael_file = "cache/factors-carmichael.storable";

my $carmichael = retrieve($carmichael_file);

my %table = (
             885  => Math::GMPz->new("24354644805191195265"),
             2391 => Math::GMPz->new("174470770903594881"),
             2571 => Math::GMPz->new("435262925087145321"),
             2589 => Math::GMPz->new("401998541941991167041"),
             2595 => Math::GMPz->new("947087538769733505"),
             2685 => Math::GMPz->new("114593508055911048606465"),
             2949 => Math::GMPz->new("13053581557039793157"),
             3147 => Math::GMPz->new("318549090992852721"),
             3327 => Math::GMPz->new("98941967334275513001"),
             3561 => Math::GMPz->new("5989287485839308321"),
             3687 => Math::GMPz->new("524511440578928001"),
             3777 => Math::GMPz->new("1987332185274308097"),
             3921 => Math::GMPz->new("8043938618249590401"),
             3945 => Math::GMPz->new("175151119571122982145"),
             3957 => Math::GMPz->new("2066101438765353669681"),
             4281 => Math::GMPz->new("37632639226277034321"),
             4317 => Math::GMPz->new("31061731865190946305"),
             4395 => Math::GMPz->new("30796418521959806145"),
             4461 => Math::GMPz->new("9986032751063139201"),
             4479 => Math::GMPz->new("206116489352712476721"),
             4569 => Math::GMPz->new("2095688354138593761"),
             4659 => Math::GMPz->new("6186353915948077761"),
             4755 => Math::GMPz->new("8013602942157895592385"),
             5199 => Math::GMPz->new("14273651174491346792001"),
             5205 => Math::GMPz->new("916541202603455265"),
             5469 => Math::GMPz->new("1114028845968724401"),
             5721 => Math::GMPz->new("731330689239874466601"),
             5739 => Math::GMPz->new("1454162635820073015201"),
             5745 => Math::GMPz->new("11247058570079728806193785"),
             5847 => Math::GMPz->new("333659645452179201"),
             5991 => Math::GMPz->new("513225718822306281"),
             6081 => Math::GMPz->new("3719863875476635754001"),
             6117 => Math::GMPz->new("155430091992394720257"),
             6189 => Math::GMPz->new("17175295397421257601"),
             6285 => Math::GMPz->new("6728010826528205985"),
             6297 => Math::GMPz->new("19389827292624042801"),
             6333 => Math::GMPz->new("9807699276298043121"),
             6423 => Math::GMPz->new("1084527196278756082161"),
             6459 => Math::GMPz->new("4249657817506137921"),
             6621 => Math::GMPz->new("192752970457624765761"),
             6801 => Math::GMPz->new("2642845284362940801"),
             6819 => Math::GMPz->new("11595472526856600705"),
             6927 => Math::GMPz->new("4729297330092026854401"),
             6999 => Math::GMPz->new("5544401350974184821"),
             7005 => Math::GMPz->new("602676024377414549745"),
             7017 => Math::GMPz->new("5829210869029084461"),
             7185 => Math::GMPz->new("505228540626753945"),
             7377 => Math::GMPz->new("1043689041704091875652561"),
             7431 => Math::GMPz->new("30090648873754779465"),
             7491 => Math::GMPz->new("1116889871166813381"),
             7635 => Math::GMPz->new("242828376142971345"),
             7737 => Math::GMPz->new("2996101935927155553"),
             7971 => Math::GMPz->new("2996101935927155553"),
             8061 => Math::GMPz->new("332680430305042401"),
             8079 => Math::GMPz->new("87027882027226845393921"),
             8133 => Math::GMPz->new("26459729919429771475281"),
             8331 => Math::GMPz->new("8846470928683112890881"),
             8355 => Math::GMPz->new("6728010826528205985"),
             8511 => Math::GMPz->new("803779319037774333801"),
             8535 => Math::GMPz->new("7054680006064724777745"),
             8709 => Math::GMPz->new("47680537491543886991601"),
             8727 => Math::GMPz->new("86047841876705126601"),
             8805 => Math::GMPz->new("5381407173960696398913345"),
             8817 => Math::GMPz->new("129588850685420778994161"),
             8871 => Math::GMPz->new("7467167622488707212801"),
             8889 => Math::GMPz->new("228249992057250389135001"),
             8895 => Math::GMPz->new("161053591977104597648385"),
             8985 => Math::GMPz->new("3855139981347264164985"),
             8997 => Math::GMPz->new("1776051810626544336705"),
             9069 => Math::GMPz->new("3257507467183865324001"),
             9249 => Math::GMPz->new("20807336597168475201"),
             9267 => Math::GMPz->new("179488857170149499841"),
             9357 => Math::GMPz->new("751190089030052734185"),
             9501 => Math::GMPz->new("10234377578232497043201"),
             9627 => Math::GMPz->new("7047849400095948081"),
             9705 => Math::GMPz->new("13630051725155410947585"),
             9771 => Math::GMPz->new("97629125640896501961"),
             9885 => Math::GMPz->new("22544660102863908989505"),
             9897 => Math::GMPz->new("420671308861831161"),
            );

my @cyclic     = map { $_ + 0 } keys %table;
my $cyclic_lcm = Math::Prime::Util::GMP::lcm(@cyclic);

my $z = Math::GMPz::Rmpz_init();

while (my ($n, $value) = each %$carmichael) {

    if (Math::Prime::Util::GMP::gcd($n, $cyclic_lcm) eq '1') {
        next;
    }

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

    foreach my $c (@cyclic) {
        if (Math::GMPz::Rmpz_divisible_ui_p($z, $c)) {
            if (Math::GMPz::Rmpz_cmp($z, $table{$c}) < 0) {
                printf("%4d: %25s (was %s)\n", $c, $z, $table{$c});
                $table{$c} = Math::GMPz::Rmpz_init_set($z);
            }
        }
    }
}

__END__
 885:  3399464645479365585 (was 24354644805191195265)
2589:  1457666333074319001 (was 401998541941991167041)
2595:    26771806123726665 (was 947087538769733505)
2949:    98362858625230161 (was 13053581557039793157)
3147:   147227530193090817 (was 318549090992852721)
3327:   438224275059528441 (was 98941967334275513001)
3921:  3308014622774231385 (was 8043938618249590401)
4281:    83031469887726921 (was 37632639226277034321)
4395:   218395364809636785 (was 30796418521959806145)
4659:    67813812914197281 (was 6186353915948077761)
4755: 10615749947367669105 (was 8013602942157895592385)
5739:   401796891724037601 (was 1454162635820073015201)
5991:    11963965077257649 (was 513225718822306281)
6189:   199784592656012001 (was 17175295397421257601)
6333:  7425044769846048801 (was 9807699276298043121)
6423:    29451778920576321 (was 1084527196278756082161)
6459:   110092137342844161 (was 4249657817506137921)
6801:    59288657066862081 (was 2642845284362940801)
6819:    11906391780675393 (was 11595472526856600705)
6999:   825621075523244001 (was 5544401350974184821)
7017:   350394397155781665 (was 5829210869029084461)
7971:   174291106521315201 (was 2996101935927155553)
8133:   147729515368989201 (was 26459729919429771475281)
8331:  1430818776987924801 (was 8846470928683112890881)
8511:  3008484874098504321 (was 803779319037774333801)
8727:   417473276486834481 (was 86047841876705126601)
8817:   227036755552727121 (was 129588850685420778994161)
8895:   572646898682000385 (was 161053591977104597648385)
8985:  1254323866883045505 (was 3855139981347264164985)
8997:  1013209278771288369 (was 1776051810626544336705)
9069:    15235791299472129 (was 3257507467183865324001)
9249:   408667965568184001 (was 20807336597168475201)
9267:   836886399144313281 (was 179488857170149499841)
9357:   799514199859612161 (was 751190089030052734185)
9705: 12463703566675736145 (was 13630051725155410947585)
9771:   101817952350880305 (was 97629125640896501961)
9885:  5954666714900228865 (was 22544660102863908989505)

 885:      23637590197922787585 (was 24354644805191195265)
8985:      30796418521959806145 (was 3855139981347264164985)
8895:    1776051810626544336705 (was 161053591977104597648385)
9885:      24711257219664352065 (was 22544660102863908989505)
8895:      99048817349242963665 (was 1776051810626544336705)