Lucas-Carmichael numbers: Difference between revisions
Content added Content deleted
(added Raku programming solution) |
(Added Python) |
||
Line 495: | Line 495: | ||
9: 791 |
9: 791 |
||
10: 1,840 |
10: 1,840 |
||
</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 |
|||
</pre> |
</pre> |
||