Lucas-Carmichael numbers: Difference between revisions
added Raku programming solution
m (→{{header|Phix}}: notonline tag) |
(added Raku programming solution) |
||
Line 496:
10: 1,840
</pre>
=={{header|Raku}}==
{{trans|Perl}}
<syntaxhighlight lang="raku" line># 20231224 Raku programming solution
use Math::Root;
use Math::Primesieve;
my @primes = Math::Primesieve.primes(100_000); # Primorial_numbers#Raku
sub primorial($n) { [*] @primes[^$n] }
sub divceil ($x, $y) { ($x %% $y ?? 0 !! 1) + $x div $y } # ceil(x/y)
sub invmod($n, $modulo) { # rosettacode.org/wiki/Modular_inverse#Raku
my ($c, $d, $uc, $vc, $ud, $vd, $q) = ($n % $modulo, $modulo, 1, 0, 0, 1);
while $c != 0 {
($q, $c, $d) = ($d div $c, $d % $c, $c);
($uc, $vc, $ud, $vd) = ($ud - $q×$uc, $vd - $q×$vc, $uc, $vc);
}
return $ud % $modulo;
}
sub LC_in_range ($A is copy, $B, $k) {
my ($max_p, @LC) = sqrt($B + 1) - 1;
$A = max(primorial($k + 1) +> 1, $A);
sub SUB($m, $L, $lo is copy, $k) {
my $hi = ( $k == 1 ) ?? ($B div $m) !! iroot ($B div $m), $k;
return if $lo > $hi;
if $k == 1 {
$hi = $max_p if $hi > $max_p;
$lo = max($lo, divceil($A, $m));
return if $lo > $hi;
my $t = $L - invmod($m, $L);
$t += $L while $t < $lo;
for $t, $t+$L ... $hi -> $p {
if $p.is-prime {
my $n = $m * $p;
@LC.push($n) if ($n + 1) %% ($p + 1);
}
}
return;
}
for Math::Primesieve.primes($lo, $hi) -> $p {
if ($m gcd ($p + 1)) == 1 {
SUB($m * $p, ($L lcm ($p + 1)), $p + 1, $k - 1)
}
}
};
SUB(1, 1, 3, $k);
return @LC.sort;
}
sub LC_with_n_primes ($n) {
return if $n < 3;
my $y = 2 * ( my $x = primorial($n + 1) +> 1);
loop {
my @LC = LC_in_range($x, $y, $n);
return @LC[0] if @LC.Bool;
$x = $y + 1;
$y = 2 * $x;
}
}
sub LC_count ($A, $B) {
my $count = 0;
for 3 .. Inf -> $k {
last if primorial($k + 1) / 2 > $B;
$count += LC_in_range($A, $B, $k).elems
}
return $count;
}
say "Least Lucas-Carmichael number with n prime factors:";
for 3 .. 12 -> $n { printf("%2d: %d\n", $n, LC_with_n_primes($n)) }
say "\nNumber of Lucas-Carmichael numbers less than 10^n:";
my $acc = 0;
for 1 .. 10 -> $n {
my $c = LC_count(10**($n - 1), 10**$n);
printf("%2d: %s\n", $n, $acc + $c);
$acc += $c
}</syntaxhighlight>
Output is the same as Perl.
=={{header|Sidef}}==
| |||