Anonymous user
Chernick's Carmichael numbers: Difference between revisions
→{{header|Julia}}
m (→with cheat) |
|||
Line 780:
(takes ~6.5 minutes)
=={{header|Nim}}==
Until a(9) a simple primality test using divisions by odd numbers is sufficient. But for a(10), it is necessary to improve the test. We have used here some optimizations found in other solutions:
:– eliminating multiples of 3, 5, 7, 11, 13, 17, 19, 23;
:– using a probability test which implies to use big integers; so, we have to convert the number to check to a big integer;
:– for n >= 5, checking only values of m which are multiple of 5 (in fact, we check only the multiples of 5 × 2^(n-4).
With these optimizations, the program executes in 4-5 minutes.
<lang Nim>import strutils, sequtils
import bignum
const
Max = 10
Factors: array[3..Max, int] = [1, 1, 2, 4, 8, 16, 32, 64] # 1 for n=3 then 2^(n-4).
FirstPrimes = [3, 5, 7, 11, 13, 17, 19, 23]
#---------------------------------------------------------------------------------------------------
iterator factors(n, m: Natural): Natural =
## Yield the factors of U(n, m).
yield 6 * m + 1
yield 12 * m + 1
var k = 2
for _ in 1..(n - 2):
yield 9 * k * m + 1
inc k, k
#---------------------------------------------------------------------------------------------------
proc mayBePrime(n: int): bool =
## First primality test.
if n < 23: return true
for p in FirstPrimes:
if n mod p == 0:
return false
result = true
#---------------------------------------------------------------------------------------------------
proc isChernick(n, m: Natural): bool =
## Check if U(N, m) if a Chernick-Carmichael number.
# Use the first and quick test.
for factor in factors(n, m):
if not factor.mayBePrime():
return false
# Use the slow probability test (need to use a big int).
for factor in factors(n, m):
if probablyPrime(newInt(factor), 25) == 0:
return false
result = true
#---------------------------------------------------------------------------------------------------
proc a(n: Natural): tuple[m: Natural, factors: seq[Natural]] =
## For a given "n", find the smallest Charnick-Carmichael number.
var m: Natural = 0
var incr = (if n >= 5: 5 else: 1) * Factors[n] # For n>= 5, a(n) is a multiple of 5.
while true:
inc m, incr
if isChernick(n, m):
return (m, toSeq(factors(n, m)))
#———————————————————————————————————————————————————————————————————————————————————————————————————
import strformat
for n in 3..Max:
let (m, factors) = a(n)
stdout.write fmt"a({n}) = U({n}, {m}) = "
var s = ""
for factor in factors:
s.addSep(" × ")
s.add($factor)
stdout.write s, '\n'</lang>
{{out}}
<pre>a(3) = U(3, 1) = 7 × 13 × 19
a(4) = U(4, 1) = 7 × 13 × 19 × 37
a(5) = U(5, 380) = 2281 × 4561 × 6841 × 13681 × 27361
a(6) = U(6, 380) = 2281 × 4561 × 6841 × 13681 × 27361 × 54721
a(7) = U(7, 780320) = 4681921 × 9363841 × 14045761 × 28091521 × 56183041 × 112366081 × 224732161
a(8) = U(8, 950560) = 5703361 × 11406721 × 17110081 × 34220161 × 68440321 × 136880641 × 273761281 × 547522561
a(9) = U(9, 950560) = 5703361 × 11406721 × 17110081 × 34220161 × 68440321 × 136880641 × 273761281 × 547522561 × 1095045121
a(10) = U(10, 3208386195840) = 19250317175041 × 38500634350081 × 57750951525121 × 115501903050241 × 231003806100481 × 462007612200961 × 924015224401921 × 1848030448803841 × 3696060897607681 × 7392121795215361</pre>
=={{header|PARI/GP}}==
| |||