Lucas-Carmichael numbers

From Rosetta Code
Revision as of 07:00, 14 December 2023 by Trizen (talk | contribs) (create draft task)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Lucas-Carmichael numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A Lucas-Carmichael number, is a squarefree composite integer n such that p+1 divides n+1 for all the prime factors p of n.

Task

Write a function that generates all the Lucas-Carmichael numbers with n prime factors in a given range [A, B].

  • Show the smallest Lucas-Carmichael with n prime factors, for n = 3..12.
  • Show the count of Lucas-Carmichael numbers less than 10^n, for n = 1..10.


Algorithm
Algorithm for generating Lucas-Carmichael numbers with n prime factors
Algorithm for generating Lucas-Carmichael numbers with n prime factors


See also


Julia

using Primes

const BIG = false       # true to use big integers

function big_prod(arr)
    BIG || return prod(arr)
    r = big(1)
    for n in arr
        r *= n
    end
    return r
end

function lucas_carmichael(A, B, k)

    LC = []
    max_p = isqrt(B+1)-1
    A = max(A, fld(big_prod(primes(prime(k+1))), 2))

    F = function(m, L, lo, k)

        hi = round(Int64, fld(B, m)^(1/k))

        if (lo > hi)
            return nothing
        end

        if (k == 1)

            hi = min(hi, max_p)
            lo = round(Int64, max(lo, cld(A, m)))
            lo > hi && return nothing

            t = L - invmod(m, L)
            t > hi && return nothing

            while (t < lo)
                t += L
            end

            for p in t:L:hi
                if (isprime(p))
                    n = m*p
                    if ((n+1) % (p+1) == 0)
                        push!(LC, n)
                    end
                end
            end

            return nothing
        end

        for p in primes(lo, hi)
            if (gcd(m, p+1) == 1)
                F(m*p, lcm(L, p+1), p+1, k-1)
            end
        end
    end

    F((BIG ? big(1) : 1), (BIG ? big(1) : 1), 3, k)

    return sort(LC)
end

function LC_with_n_primes(n)

    n < 3 && return nothing

    x = big_prod(primes(prime(n + 1))) >> 1
    y = 2 * x

    while true
        LC = lucas_carmichael(x, y, n)
        if (length(LC) >= 1)
            return LC[1]
        end
        x = y + 1
        y = 2 * x
    end
end

println("Least Lucas-Carmichael number with n prime factors:")

for n in 3:12
    println([n, LC_with_n_primes(n)])
end

function LC_count(A, B)
    count = 0
    for k in 3:10^6
        if (big_prod(primes(prime(k+1)))/2 > B)
            break
        end
        count += length(lucas_carmichael(A, B, k))
    end
    return count
end

println("\nNumber of Lucas-Carmichael numbers less than 10^n:")

for n in 1:10
    println([n, LC_count(1, 10^n)])
end
Output:
Least Lucas-Carmichael number with n prime factors:
[3, 399]
[4, 8855]
[5, 588455]
[6, 139501439]
[7, 3512071871]
[8, 199195047359]
[9, 14563696180319]
[10, 989565001538399]
[11, 20576473996736735]
[12, 4049149795181043839]

Number of Lucas-Carmichael numbers less than 10^n:
[1, 0]
[2, 0]
[3, 2]
[4, 8]
[5, 26]
[6, 60]
[7, 135]
[8, 323]
[9, 791]
[10, 1840]

PARI/GP

lucas_carmichael(A, B, k) = {
    A=max(A, vecprod(primes(k+1))\2);
    my(max_p=sqrtint(B+1)-1);
    (f(m, l, lo, k) =
        my(list=List());
        my(hi=sqrtnint(B\m, k));
        if(lo > hi, return(list));
        if(k==1,
            hi = min(hi, max_p);
            lo=max(lo, ceil(A/m));
            my(t=lift(-1/Mod(m,l)));
            while(t < lo, t += l);
            forstep(p=t, hi, l,
                if(isprime(p),
                    my(n=m*p);
                    if((n+1)%(p+1) == 0, listput(list, n));
                );
            ),
        \\ else
            forprime(p=lo, hi,
                if(gcd(m, p+1) == 1,
                    list=concat(list, f(m*p, lcm(l, p+1), p+1, k-1))
                );
            );
        );
        list;
    );
    vecsort(Vec(f(1, 1, 3, k)));
};

LC_count(n) = {
    my(count=0);
    for(k=3, oo,
        if(vecprod(primes(k+1))\2 > n, break);
        count += #lucas_carmichael(1, n, k)
    );
    count;
};

LC_with_n_primes(n) = {
    if(n < 3, return());
    my(x=vecprod(primes(n+1))\2, y=2*x);
    while(1,
        my(v=lucas_carmichael(x,y,n));
        if(#v >= 1, return(v[1]));
        x=y+1; y=2*x;
    );
};

print("Least Lucas-Carmichael number with n prime factors:")
for(n=3, 12, print([n, LC_with_n_primes(n)]));

print("\nNumber of Lucas-Carmichael numbers less than 10^n:")
for(n=1, 10, print([n, LC_count(10^n)]));
Output:
Least Lucas-Carmichael number with n prime factors:
[3, 399]
[4, 8855]
[5, 588455]
[6, 139501439]
[7, 3512071871]
[8, 199195047359]
[9, 14563696180319]
[10, 989565001538399]
[11, 20576473996736735]
[12, 4049149795181043839]

Number of Lucas-Carmichael numbers less than 10^n:
[1, 0]
[2, 0]
[3, 2]
[4, 8]
[5, 26]
[6, 60]
[7, 135]
[8, 323]
[9, 791]
[10, 1840]

Perl

use 5.020;
use ntheory      qw(:all);
use experimental qw(signatures);

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

sub LC_in_range ($A, $B, $k) {

    my @LC;
    my $max_p = sqrtint($B + 1) - 1;

    $A = vecmax(pn_primorial($k + 1) >> 1, $A);

    sub ($m, $L, $lo, $k) {

        my $hi = rootint(int($B / $m), $k);

        return if ($lo > $hi);

        if ($k == 1) {

            $hi = $max_p if ($hi > $max_p);
            $lo = vecmax($lo, divceil($A, $m));
            $lo > $hi && return;

            my $t = $L - invmod($m, $L);
            $t += $L while ($t < $lo);

            for (my $p = $t ; $p <= $hi ; $p += $L) {
                if (is_prime($p)) {
                    my $n = $m * $p;
                    if (($n + 1) % ($p + 1) == 0) {
                        push @LC, $n;
                    }
                }
            }

            return;
        }

        foreach my $p (@{primes($lo, $hi)}) {
            if (gcd($m, $p + 1) == 1) {
                __SUB__->($m * $p, lcm($L, $p + 1), $p + 1, $k - 1);
            }
        }
      }
      ->(1, 1, 3, $k);

    return sort { $a <=> $b } @LC;
}

sub LC_with_n_primes ($n) {
    return if ($n < 3);

    my $x = pn_primorial($n + 1) >> 1;
    my $y = 2 * $x;

    for (; ;) {
        my @LC = LC_in_range($x, $y, $n);
        @LC and return $LC[0];
        $x = $y + 1;
        $y = 2 * $x;
    }
}

sub LC_count ($A, $B) {
    my $count = 0;
    for (my $k = 3 ; ; ++$k) {
        if (pn_primorial($k + 1) / 2 > $B) {
            last;
        }
        my @LC = LC_in_range($A, $B, $k);
        $count += @LC;
    }
    return $count;
}

say "Least Lucas-Carmichael number with n prime factors:";

foreach my $n (3 .. 12) {
    printf("%2d: %s\n", $n, LC_with_n_primes($n));
}

say "\nNumber of Lucas-Carmichael numbers less than 10^n:";

my $acc = 0;
foreach my $n (1 .. 10) {
    my $c = LC_count(10**($n - 1), 10**$n);
    printf("%2d: %s\n", $n, $acc + $c);
    $acc += $c;
}
Output:
Least Lucas-Carmichael number with n prime factors:
 3: 399
 4: 8855
 5: 588455
 6: 139501439
 7: 3512071871
 8: 199195047359
 9: 14563696180319
10: 989565001538399
11: 20576473996736735
12: 4049149795181043839

Number of Lucas-Carmichael numbers less than 10^n:
 1: 0
 2: 0
 3: 2
 4: 8
 5: 26
 6: 60
 7: 135
 8: 323
 9: 791
10: 1840

Sidef

The function is also built-in as n.lucas_carmichael(A,B). 

func LC_in_range(A, B, k) {

    var LC = []

    func (m, L, lo, k) {

        var hi = idiv(B,m).iroot(k)

        if (lo > hi) {
            return nil
        }

        if (k == 1) {

            hi = min(B.isqrt, hi)
            lo = max(lo, idiv_ceil(A, m))
            lo > hi && return nil

            var t = mulmod(m.invmod(L), -1, L)

            t > hi && return nil
            t += L while (t < lo)

            for p in (range(t, hi, L).primes) {
                with (m*p) {|n|
                    LC << n if (p+1 `divides` n+1)
                }
            }

            return nil
        }

        each_prime(lo, hi, {|p|
            __FUNC__(m*p, lcm(L, p+1), p+1, k-1) if m.is_coprime(p+1)
        })
    }(1, 1, 3, k)

    return LC.sort
}

func LC_with_n_primes(n) {
    return nil if (n < 3)

    var x = pn_primorial(n+1)/2
    var y = 2*x

    loop {
        var arr = LC_in_range(x,y,n)
        arr && return arr[0]
        x = y+1
        y = 2*x
    }
}

func LC_count(A, B) {
    var count = 0
    for k in (3..Inf) {
        if (pn_primorial(k+1)/2 > B) {
            break
        }
        count += LC_in_range(A,B,k).len
    }
    return count
}

say "Least Lucas-Carmichael number with n prime factors:"

for n in (3..12) {
    say "#{'%2d'%n}: #{LC_with_n_primes(n)}"
}

say "\nNumber of Lucas-Carmichael numbers less than 10^n:"

var acc = 0
for n in (1..10) {
    var c = LC_count(10**(n-1), 10**n)
    say "#{'%2d'%n}: #{c + acc}"
    acc += c
}
Output:
Least Lucas-Carmichael number with n prime factors:
 3: 399
 4: 8855
 5: 588455
 6: 139501439
 7: 3512071871
 8: 199195047359
 9: 14563696180319
10: 989565001538399
11: 20576473996736735
12: 4049149795181043839

Number of Lucas-Carmichael numbers less than 10^n:
 1: 0
 2: 0
 3: 2
 4: 8
 5: 26
 6: 60
 7: 135
 8: 323
 9: 791
10: 1840
Retrieved from "https://rosettacode.org/wiki/Lucas-Carmichael_numbers?oldid=360557"