perl-scripts/Math/carmichael_numbers_random.pl

#!/usr/bin/perl

# Generate random Carmichael numbers of the form (k+1)*(2*k+1)*(3*k+1), where k+1, 2*k+1 and 3*k+1 are all primes.

# See also:
#   https://oeis.org/A033502 -- Carmichael numbers of the form (6*k+1)*(12*k+1)*(18*k+1)
#   https://oeis.org/A255441 -- Carmichael numbers of the form (60k+41)(90k+61)(150k+101)
#   https://oeis.org/A255514 -- Carmichael numbers of the form (24*k+13)*(72*k+37)*(192*k+97)
#   https://oeis.org/A182085 -- Carmichael numbers of the form (30k+7)*(60k+13)*(150k+31)
#   https://oeis.org/A182088 -- Carmichael numbers of the form (30n-29)*(60n-59)*(90n-89)*(180n-179)
#   https://oeis.org/A182132 -- Carmichael numbers of the form (30n-7)*(90n-23)*(300n-79)
#   https://oeis.org/A182133 -- Carmichael numbers of the form (30n-17)*(90n-53)*(150n-89)
#   https://oeis.org/A182416 -- Carmichael numbers of the form (60k+13)*(180k+37)*(300k+61)

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

use Math::GMPz;
use Math::Prime::Util::GMP qw(is_prob_prime vecprod random_ndigit_prime);

sub random_carmichael_number ($n = 20) {

    $n = 2 if ($n <= 1);

    while (1) {
        my $p = Math::GMPz::Rmpz_init_set_str(random_ndigit_prime($n), 10);
        my $k = ($p - 1);
        is_prob_prime(2*$k + 1) && is_prob_prime(3*$k + 1) or next;
        return ($p, 2*$k + 1, 3*$k + 1);
    }
}

foreach my $n (2 .. 20) {

    my @factors    = random_carmichael_number($n);
    my $carmichael = vecprod(@factors);

    say "$carmichael = ", join(' * ', @factors);
}

__END__
294409 = 37 * 73 * 109
56052361 = 211 * 421 * 631
71171308081 = 2281 * 4561 * 6841
129140929242289 = 27817 * 55633 * 83449
472631192510407921 = 428671 * 857341 * 1286011
27572283826108082569 = 1662547 * 3325093 * 4987639
345721500688805466654601 = 38624101 * 77248201 * 115872301
130699973774636844248473489 = 279281017 * 558562033 * 837843049
27673744421175202436239020169 = 1664583397 * 3329166793 * 4993750189
328972311969416805526009802207569 = 37990006297 * 75980012593 * 113970018889
2154063839571860482226489311256938129 = 710726387407 * 1421452774813 * 2132179162219
570115866940668362539466801338334994649 = 4563211789627 * 9126423579253 * 13689635368879
1782421577597012564570834220077888509756969 = 66724663694947 * 133449327389893 * 200173991084839
52582793280275762357474570728765725923205529 = 206172530234557 * 412345060469113 * 618517590703669
278521214364869103131896930517366707497856421161 = 3593925000970261 * 7187850001940521 * 10781775002910781
1033219900193456185960963387986087314925660018643009 = 55634881918514887 * 111269763837029773 * 166904645755544659
1081644507889807242059050179401322818854661656619742361 = 564908053691846461 * 1129816107383692921 * 1694724161075539381
341413647754278719970853443358101430514668165478272427161 = 3846300480078170011 * 7692600960156340021 * 11538901440234510031
6271289738172907436343660234664403558286290715038000756209 = 10148500369293939337 * 20297000738587878673 * 30445501107881818009