Lucas-Carmichael numbers: Difference between revisions

</pre>

=={{header|Python}}==

Uses the [[wp:SymPy|SymPy]] library.

<syntaxhighlight lang="python">from sympy.ntheory import sieve, isprime, prime

from sympy.core import mod_inverse, integer_nthroot

from math import lcm, gcd, isqrt

def lucas_carmichael(A, B, n):

max_p = isqrt(B)+1

def f(m, l, lo, k):

hi = (integer_nthroot(B // m, k))[0]+1

if lo > hi: return

if k == 1:

lo = max(lo, A // m + (1 if A % m else 0))

hi = min(hi, max_p)

u = l - mod_inverse(m, l)

while u < lo: u += l

if u > hi: return

for p in range(u, hi, l):

if (m*p+1) % (p+1) == 0 and isprime(p):

yield m*p

else:

for p in sieve.primerange(lo, hi):

if gcd(m, p+1) == 1:

yield from f(m*p, lcm(l, p+1), p + 2, k - 1)

return sorted(f(1, 1, 3, n))

def LC_with_n_primes(n):

x = 2

y = 2*x

while True:

LC = lucas_carmichael(x, y, n)

if len(LC) >= 1: return LC[0]

x = y+1

y = 2*x

def LC_count(A, B):

k = 3

l = 3*5*7

count = 0

while l < B:

count += len(lucas_carmichael(A, B, k))

k += 1

l *= prime(k+1)

return count

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

for n in range(3, 12+1):

print("%2d: %d" % (n, LC_with_n_primes(n)))

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

for n in range(1, 10+1):

print("%2d: %d" % (n, LC_count(1, 10**n)))</syntaxhighlight>

{{out}}

<pre>

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