I'm trying to list all of the Carmichael numbers under 10000, however, I think I have issue with the print_carmichael function. For some reason, it does not print all of the n values when the is_carmichael is true.
def is_carmichael(n):
b = 2
while b<n:
if (gcd(b, n) == 1):
if (pow(b, n - 1, n) != 1):
return 0
b = b + 1
return 1
def print_carmichael(max):
for n in range(2, max):
if is_carmichael(n):
print(n)
return 0
The primary issue I see is that you're not filtering out prime numbers as Wolfram MathWorld notes:
A Carmichael number is an odd composite number
from math import gcd
def is_prime(number):
if number <= 2:
return number == 2
if number % 2 == 0:
return False
for divisor in range(3, int(number ** 0.5) + 1, 2):
if number % divisor == 0:
return False
return True
def is_carmichael(n):
# a Carmichael number is an odd composite number
if n <= 2 or n % 2 == 0 or is_prime(n):
return False
for a in range(3, n, 2):
if gcd(a, n) == 1:
if pow(a, n - 1, n) != 1:
return False
return True
def print_carmichael(maximum):
for number in range(maximum):
if is_carmichael(number):
print(number)
print_carmichael(100_000)
OUTPUT
% python3 test.py
561
1105
1729
2465
2821
6601
8911
10585
15841
29341
41041
46657
52633
62745
63973
75361
%
There's probably a more efficient way to do the composite test but you get the idea. We can simplify this code, at a cost of speed, by using the logic in is_charmichael() itself to filter out primes and tossing our explicit is_prime() function:
def is_carmichael(n):
# a Carmichael number is an odd number
if n <= 2 or n % 2 == 0:
return False
may_be_prime = True
for a in range(3, n, 2):
if gcd(a, n) == 1:
if pow(a, n - 1, n) != 1:
return False
else:
may_be_prime = False
return not may_be_prime