Anonymous user
Chernick's Carmichael numbers: Difference between revisions
Python example
(Added Wren) |
(Python example) |
||
Line 1,147:
9: 5703361*11406721*17110081*34220161*68440321*136880641*273761281*547522561*1095045121 = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
=={{header|Python}}==
<lang python>
"""
Python implementation of
http://rosettacode.org/wiki/Chernick%27s_Carmichael_numbers
"""
# use sympy for prime test
from sympy import isprime
# based on C version
def primality_pretest(k):
if not (k % 3) or not (k % 5) or not (k % 7) or not (k % 11) or not(k % 13) or not (k % 17) or not (k % 19) or not (k % 23):
return (k <= 23)
return True
def is_chernick(n, m):
t = 9 * m
if not primality_pretest(6 * m + 1):
return False
if not primality_pretest(12 * m + 1):
return False
for i in range(1,n-1):
if not primality_pretest((t << i) + 1):
return False
if not isprime(6 * m + 1):
return False
if not isprime(12 * m + 1):
return False
for i in range(1,n - 1):
if not isprime((t << i) + 1):
return False
return True
for n in range(3,10):
if n > 4:
multiplier = 1 << (n - 4)
else:
multiplier = 1
if n > 5:
multiplier *= 5
k = 1
while True:
m = k * multiplier
if is_chernick(n, m):
print("a("+str(n)+") has m = "+str(m))
break
k += 1
</lang>
{{out}}
<pre>
a(3) has m = 1
a(4) has m = 1
a(5) has m = 380
a(6) has m = 380
a(7) has m = 780320
a(8) has m = 950560
a(9) has m = 950560
</pre>
=={{header|Raku}}==
(formerly Perl 6)
| |||