lucas-carmichael_numbers_in_range_from_prime_factors.pl

#!/usr/bin/perl

# Daniel "Trizen" Șuteu
# Date: 24 September 2022
# https://github.com/trizen

# Generate all the Lucas-Carmichael numbers with n prime factors in a given range [A,B], using a given list of prime factors. (not in sorted order)

# See also:
#   https://en.wikipedia.org/wiki/Almost_prime
#   https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html

use 5.020;
use warnings;

use ntheory      qw(:all);
use experimental qw(signatures);
use List::Util   qw(uniq);

sub divceil ($x, $y) {    # ceil(x/y)
    (($x % $y == 0) ? 0 : 1) + divint($x, $y);
}

sub lucas_carmichael_numbers_in_range ($A, $B, $k, $primes, $callback) {

    $A = vecmax($A, pn_primorial($k));

    # Largest possisble prime factor for Lucas-Carmichael numbers <= B
    my $max_p = sqrtint($B);

    my @P   = sort { $a <=> $b } grep { $_ <= $max_p } uniq(@$primes);
    my $end = $#P;

    sub ($m, $lambda, $j, $k) {

        my $y = vecmin($max_p, rootint(divint($B, $m), $k));

        if ($k == 1) {

            my $x = divceil($A, $m);

            if ($P[-1] < $x) {
                return;
            }

            foreach my $i ($j .. $end) {
                my $p = $P[$i];

                last if ($p > $y);
                next if ($p < $x);

                my $t = $m * $p;

                if (($t + 1) % $lambda == 0 and ($t + 1) % ($p + 1) == 0) {
                    $callback->($t);
                }
            }

            return;
        }

        foreach my $i ($j .. $end) {
            my $p = $P[$i];
            last if ($p > $y);

            gcd($m, $p + 1) == 1 or next;

            # gcd($m*$p, divisor_sum($m*$p)) == 1 or die "$m*$p: not Lucas-cyclic";

            __SUB__->($m * $p, lcm($lambda, $p + 1), $i + 1, $k - 1);
        }
      }
      ->(1, 1, 0, $k);
}

my $lambda = 5040;
my @primes = grep { $_ > 2 and $lambda % $_ != 0 and is_prime($_) } map { $_ - 1 } divisors($lambda);

foreach my $k (3 .. 6) {
    my @arr;
    lucas_carmichael_numbers_in_range(1, 10**(2 * $k), $k, \@primes, sub ($n) { push @arr, $n });
    say "$k: ", join(', ', sort { $a <=> $b } @arr);
}

__END__
3: 20999, 46079, 63503, 76751, 88559, 152279, 155819, 230159, 388079, 761039
4: 81719, 357599, 895679, 1097459, 2150819, 2193119, 2581319, 3228119, 6023039, 8159759, 9349919, 12791519, 14800799, 18119519, 21490919, 38534327, 64585079
5: 6539819, 34541639, 49591919, 77350559, 83618639, 96080039, 157169879, 164613599, 183259439, 190079567, 307409759, 308810879, 690313679, 715317119, 728655479, 1053082799, 1122191279, 1170131759, 1206682559, 1459340639, 1532480543, 1763936999, 2049702479, 2159807159, 2576523599, 2596839839, 3641725079, 3986123399, 4038577199, 4358632319, 5165929439, 5206299839, 5424849359, 6709316039, 7418764079, 8177790599, 8897595839, 9578393999
6: 577901519, 1361371679, 1373537759, 1638550199, 2828024639, 2888673983, 2928121559, 3080459759, 4805735759, 4864901327, 5287495499, 5800236959, 6416323199, 7437699359, 7867853279, 9779978879, 11550463679, 11672334239, 13356002519, 13425488999, 14413764959, 15123923639, 15211879199, 15444409679, 15562456559, 16386375599, 17095979879, 17510861339, 17959287359, 17965888919, 19178943839, 19621223999, 20078753519, 21093389999, 23231683439, 23998272479, 25648570079, 26311503959, 29161838879, 29812502159, 32093601119, 39033948239, 41340843599, 46096729559, 52810178399, 52915495919, 54527266079, 61450169759, 62065553759, 70523812799, 71361474239, 79214320079, 81732797999, 90622974959, 92296542239, 99952937279, 102454676519, 120477765239, 126759626279, 128758238279, 137991228479, 138213779759, 142528198679, 146361334559, 148323320279, 149896068839, 153340029359, 158221682639, 159322390559, 159890779439, 160255240739, 161112901319, 171015667199, 173334520799, 180069704639, 180965337839, 187380048239, 202229818559, 206865082619, 220211424719, 222446579039, 232442534519, 233155551599, 253483070399, 296032324559, 297059797439, 307853073359, 343190741039, 353042872559, 363624130799, 380506890959, 385801834319, 392952329279, 399641253479, 405417742379, 412826561279, 487915989119, 509234910239, 521538610319, 522204006239, 589571193959, 648004578479, 654467622479, 675275252399, 741269849039, 745580820599, 756101062079, 784130932079, 792545816159, 806516068679, 823432111199, 827953257599, 837926369279, 854535596039, 906105710159