Rosetta Code

Chernick's Carmichael numbers: Difference between revisions

Page Discussion

Chernick's Carmichael numbers (view source)

Revision as of 12:26, 17 November 2023

59,091 bytes added ,  6 months ago
m
→‎{{header|Wren}}: Minor tidy
(→‎{{header|zkl}}: added code)
m (→‎{{header|Wren}}: Minor tidy)
 
(38 intermediate revisions by 15 users not shown)
Line 1:
{{draft task|Mathematics}}
[[category:Prime Numbers]]
In 1939, Jack Chernick proved that, for '''n ≥ 3''' and '''m ≥ 1''':
 
Line 30 ⟶ 31:
 
* Compute '''a(n)''' for '''n = 3..9'''.
* Optional: find '''a(10)'''.
 
* Optional: try to find '''a(10)'''. (this may take a long time)
 
 
 
Line 50 ⟶ 49:
 
 
; Related tasks
* [[Carmichael 3 strong pseudoprimes]]
 
<br><br>
=={{header|C}}==
{{libheader|GMP}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
 
typedef unsigned long long int u64;
 
#define TRUE 1
#define FALSE 0
 
int primality_pretest(u64 k) {
if (!(k % 3) || !(k % 5) || !(k % 7) || !(k % 11) || !(k % 13) || !(k % 17) || !(k % 19) || !(k % 23)) return (k <= 23);
return TRUE;
}
 
int probprime(u64 k, mpz_t n) {
mpz_set_ui(n, k);
return mpz_probab_prime_p(n, 0);
}
 
int is_chernick(int n, u64 m, mpz_t z) {
u64 t = 9 * m;
if (primality_pretest(6 * m + 1) == FALSE) return FALSE;
if (primality_pretest(12 * m + 1) == FALSE) return FALSE;
for (int i = 1; i <= n - 2; i++) if (primality_pretest((t << i) + 1) == FALSE) return FALSE;
if (probprime(6 * m + 1, z) == FALSE) return FALSE;
if (probprime(12 * m + 1, z) == FALSE) return FALSE;
for (int i = 1; i <= n - 2; i++) if (probprime((t << i) + 1, z) == FALSE) return FALSE;
return TRUE;
}
 
int main(int argc, char const *argv[]) {
mpz_t z;
mpz_inits(z, NULL);
 
for (int n = 3; n <= 10; n ++) {
u64 multiplier = (n > 4) ? (1 << (n - 4)) : 1;
 
if (n > 5) multiplier *= 5;
 
for (u64 k = 1; ; k++) {
u64 m = k * multiplier;
 
if (is_chernick(n, m, z) == TRUE) {
printf("a(%d) has m = %llu\n", n, m);
break;
}
}
}
 
return 0;
}</syntaxhighlight>
{{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
a(10) has m = 3208386195840
</pre>
=={{header|C++}}==
{{libheader|GMP}}
<syntaxhighlight lang="cpp">#include <gmp.h>
#include <iostream>
 
using namespace std;
 
typedef unsigned long long int u64;
 
bool primality_pretest(u64 k) { // for k > 23
 
if (!(k % 3) || !(k % 5) || !(k % 7) || !(k % 11) ||
!(k % 13) || !(k % 17) || !(k % 19) || !(k % 23)
) {
return (k <= 23);
}
 
return true;
}
 
bool probprime(u64 k, mpz_t n) {
mpz_set_ui(n, k);
return mpz_probab_prime_p(n, 0);
}
 
bool is_chernick(int n, u64 m, mpz_t z) {
 
if (!primality_pretest(6 * m + 1)) {
return false;
}
 
if (!primality_pretest(12 * m + 1)) {
return false;
}
 
u64 t = 9 * m;
 
for (int i = 1; i <= n - 2; i++) {
if (!primality_pretest((t << i) + 1)) {
return false;
}
}
 
if (!probprime(6 * m + 1, z)) {
return false;
}
 
if (!probprime(12 * m + 1, z)) {
return false;
}
 
for (int i = 1; i <= n - 2; i++) {
if (!probprime((t << i) + 1, z)) {
return false;
}
}
 
return true;
}
 
int main() {
 
mpz_t z;
mpz_inits(z, NULL);
 
for (int n = 3; n <= 10; n++) {
 
// `m` is a multiple of 2^(n-4), for n > 4
u64 multiplier = (n > 4) ? (1 << (n - 4)) : 1;
 
// For n > 5, m is also a multiple of 5
if (n > 5) {
multiplier *= 5;
}
 
for (u64 k = 1; ; k++) {
 
u64 m = k * multiplier;
 
if (is_chernick(n, m, z)) {
cout << "a(" << n << ") has m = " << m << endl;
break;
}
}
}
 
return 0;
}</syntaxhighlight>
{{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
a(10) has m = 3208386195840
</pre>
(takes ~3.5 minutes)
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Generate Chernick's Carmichael numbers. Nigel Galloway: June 1st., 2019
let fNfMk g=letm mxk=intisPrime(sqrt(float6*m+1) g)&& isPrime(12*m+1) in&& pCache|>Seq[1..takeWhile(fun nk->n<=mx)2]|>SeqList.forall(fun n->g%isPrime(int649*(pown 2 n)>0L*m+1))
let fMk mfX k=fNSeq.initInfinite(fun n->(6L*mn+1L1)*(pown && fN2 (12L*m+1Lk-4))) && [1..k-2]|>List Seq.forallfilter(fun n->fNfMk (9L*(pownn 2Lk n)*m+1L))
let fXcherCar k=let m=Seq.initInfinitehead(funfX k) in printfn "m=%d primes n->int64 %A " m (n[6*m+1);12*(pown 2L m+1]@List.init(k-4))2) |> Seq.filter(fun n->fMk9*(pown n k2 (n+1))*m+1))
let cherCar k=let m=Seq.head(fX k) in printfn "cherCar(%d): m=%d primes -> %A " k m ([6L*m+1L;12L*m+1L]@List.init(k-2)(fun n->9L*(pown 2L (n+1))*m+1L))
[4..9] |> Seq.iter cherCar
</syntaxhighlight>
</lang>
{{out}}
<pre>
cherCar(4): m=1 primes -> [7L7; 13L13; 19L19; 37L37]
cherCar(5): m=380 primes -> [2281L2281; 4561L4561; 6841L6841; 13681L13681; 27361L27361]
cherCar(6): m=380 primes -> [2281L2281; 4561L4561; 6841L6841; 13681L13681; 27361L27361; 54721L54721]
cherCar(7): m=780320 primes -> [4681921L4681921; 9363841L9363841; 14045761L14045761; 28091521L28091521; 56183041L56183041; 112366081L112366081; 224732161L224732161]
cherCar(8): m=950560 primes -> [5703361L5703361; 11406721L11406721; 17110081L17110081; 34220161L34220161; 68440321L68440321; 136880641L136880641; 273761281L273761281; 547522561L547522561]
cherCar(9): m=950560 primes -> [5703361L5703361; 11406721L11406721; 17110081L17110081; 34220161L34220161; 68440321L68440321; 136880641L136880641; 273761281L273761281; 547522561L547522561; 1095045121L1095045121]
</pre>
=={{header|FreeBASIC}}==
===Basic only===
<syntaxhighlight lang="freebasic">#include "isprime.bas"
 
Function PrimalityPretest(k As Integer) As Boolean
Dim As Integer ppp(1 To 8) = {3,5,7,11,13,17,19,23}
For i As Integer = 1 To Ubound(ppp)
If k Mod ppp(i) = 0 Then Return (k <= 23)
Next i
Return True
End Function
 
Function isChernick(n As Integer, m As Integer) As Boolean
Dim As Integer i, t = 9 * m
If Not PrimalityPretest(6 * m + 1) Then Return False
If Not PrimalityPretest(12 * m + 1) Then Return False
For i = 1 To n-1
If Not PrimalityPretest(t * (2 ^ i) + 1) Then Return False
Next i
If Not isPrime(6 * m + 1) Then Return False
If Not isPrime(12 * m + 1) Then Return False
For i = 1 To n - 2
If Not isPrime(t * (2 ^ i) + 1) Then Return False
Next i
Return True
End Function
 
Dim As Uinteger multiplier, k, m = 1
For n As Integer = 3 To 9
multiplier = Iif (n > 4, 2 ^ (n-4), 1)
If n > 5 Then multiplier *= 5
k = 1
Do
m = k * multiplier
If isChernick(n, m) Then
Print "a(" & n & ") has m = " & m
Exit Do
End If
k += 1
Loop
Next n
Sleep</syntaxhighlight>
=={{header|Go}}==
===Basic only===
<lang go>package main
<syntaxhighlight lang="go">package main
 
import (
Line 85 ⟶ 299:
func ccFactors(n, m uint64) (*big.Int, bool) {
prod.SetUint64(6*m + 1)
if !prod.ProbablyPrime(100) {
return zero, false
}
fact.SetUint64(12*m + 1)
if !fact.ProbablyPrime(100) { // 100% accurate up to 2 ^ 64
return zero, false
}
Line 95 ⟶ 309:
for i := uint64(1); i <= n-2; i++ {
fact.SetUint64((1<<i)*9*m + 1)
if !fact.ProbablyPrime(100) {
return zero, false
}
Line 126 ⟶ 340:
func main() {
ccNumbers(3, 9)
}</langsyntaxhighlight>
 
{{out}}
Line 138 ⟶ 352:
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
===Basic plus optional===
{{libheader|GMP(Go wrapper)}}
<br>
To reach a(10) in a reasonable time, a much more efficient approach is needed.
 
The following version takes account of the optimizations referred to in the Talk page and previewed in the C++ entry above.
 
It also uses a wrapper for the C library, GMP, which despite the overhead of cgo is still much faster than Go's native big.Int library.
 
The resulting executable is several hundred times faster than before and, even on my modest Celeron @1.6GHZ, reaches a(9) in under 10ms and a(10) in about 22 minutes.
<syntaxhighlight lang="go">package main
 
import (
"fmt"
big "github.com/ncw/gmp"
)
 
const (
min = 3
max = 10
)
 
var (
prod = new(big.Int)
fact = new(big.Int)
factors = [max]uint64{}
bigFactors = [max]*big.Int{}
)
 
func init() {
for i := 0; i < max; i++ {
bigFactors[i] = big.NewInt(0)
}
}
 
func isPrimePretest(k uint64) bool {
if k%3 == 0 || k%5 == 0 || k%7 == 0 || k%11 == 0 ||
k%13 == 0 || k%17 == 0 || k%19 == 0 || k%23 == 0 {
return k <= 23
}
return true
}
 
func ccFactors(n, m uint64) bool {
if !isPrimePretest(6*m + 1) {
return false
}
if !isPrimePretest(12*m + 1) {
return false
}
factors[0] = 6*m + 1
factors[1] = 12*m + 1
t := 9 * m
for i := uint64(1); i <= n-2; i++ {
tt := (t << i) + 1
if !isPrimePretest(tt) {
return false
}
factors[i+1] = tt
}
 
for i := 0; i < int(n); i++ {
fact.SetUint64(factors[i])
if !fact.ProbablyPrime(0) {
return false
}
bigFactors[i].Set(fact)
}
return true
}
 
func prodFactors(n uint64) *big.Int {
prod.Set(bigFactors[0])
for i := 1; i < int(n); i++ {
prod.Mul(prod, bigFactors[i])
}
return prod
}
 
func ccNumbers(start, end uint64) {
for n := start; n <= end; n++ {
mult := uint64(1)
if n > 4 {
mult = 1 << (n - 4)
}
if n > 5 {
mult *= 5
}
m := mult
for {
if ccFactors(n, m) {
num := prodFactors(n)
fmt.Printf("a(%d) = %d\n", n, num)
fmt.Printf("m(%d) = %d\n", n, m)
fmt.Println("Factors:", factors[:n], "\n")
break
}
m += mult
}
}
}
 
func main() {
ccNumbers(min, max)
}</syntaxhighlight>
 
{{out}}
<pre>
a(3) = 1729
m(3) = 1
Factors: [7 13 19]
 
a(4) = 63973
m(4) = 1
Factors: [7 13 19 37]
 
a(5) = 26641259752490421121
m(5) = 380
Factors: [2281 4561 6841 13681 27361]
 
a(6) = 1457836374916028334162241
m(6) = 380
Factors: [2281 4561 6841 13681 27361 54721]
 
a(7) = 24541683183872873851606952966798288052977151461406721
m(7) = 780320
Factors: [4681921 9363841 14045761 28091521 56183041 112366081 224732161]
 
a(8) = 53487697914261966820654105730041031613370337776541835775672321
m(8) = 950560
Factors: [5703361 11406721 17110081 34220161 68440321 136880641 273761281 547522561]
 
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
m(9) = 950560
Factors: [5703361 11406721 17110081 34220161 68440321 136880641 273761281 547522561 1095045121]
 
a(10) = 24616075028246330441656912428380582403261346369700917629170235674289719437963233744091978433592331048416482649086961226304033068172880278517841921
m(10) = 3208386195840
Factors: [19250317175041 38500634350081 57750951525121 115501903050241 231003806100481 462007612200961 924015224401921 1848030448803841 3696060897607681 7392121795215361]
</pre>
=={{header|J}}==
 
Brute force:
 
<syntaxhighlight lang="j">a=: {{)v
if.3=y do.1729 return.end.
m=. z=. 2^y-4
f=. 6 12,9*2^}.i.y-1
while.do.
uf=.1+f*m
if.*/1 p: uf do. */x:uf return.end.
m=.m+z
end.
}}</syntaxhighlight>
 
Task examples:
 
<syntaxhighlight lang="j"> a 3
1729
a 4
63973
a 5
26641259752490421121
a 6
1457836374916028334162241
a 7
24541683183872873851606952966798288052977151461406721
a 8
53487697914261966820654105730041031613370337776541835775672321
a 9
58571442634534443082821160508299574798027946748324125518533225605795841</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
 
public class ChernicksCarmichaelNumbers {
 
public static void main(String[] args) {
for ( long n = 3 ; n < 10 ; n++ ) {
long m = 0;
boolean foundComposite = true;
List<Long> factors = null;
while ( foundComposite ) {
m += (n <= 4 ? 1 : (long) Math.pow(2, n-4) * 5);
factors = U(n, m);
foundComposite = false;
for ( long factor : factors ) {
if ( ! isPrime(factor) ) {
foundComposite = true;
break;
}
}
}
System.out.printf("U(%d, %d) = %s = %s %n", n, m, display(factors), multiply(factors));
}
}
private static String display(List<Long> factors) {
return factors.toString().replace("[", "").replace("]", "").replaceAll(", ", " * ");
}
private static BigInteger multiply(List<Long> factors) {
BigInteger result = BigInteger.ONE;
for ( long factor : factors ) {
result = result.multiply(BigInteger.valueOf(factor));
}
return result;
}
private static List<Long> U(long n, long m) {
List<Long> factors = new ArrayList<>();
factors.add(6*m + 1);
factors.add(12*m + 1);
for ( int i = 1 ; i <= n-2 ; i++ ) {
factors.add(((long)Math.pow(2, i)) * 9 * m + 1);
}
return factors;
}
 
private static final int MAX = 100_000;
private static final boolean[] primes = new boolean[MAX];
private static boolean SIEVE_COMPLETE = false;
private static final boolean isPrimeTrivial(long test) {
if ( ! SIEVE_COMPLETE ) {
sieve();
SIEVE_COMPLETE = true;
}
return primes[(int) test];
}
private static final void sieve() {
// primes
for ( int i = 2 ; i < MAX ; i++ ) {
primes[i] = true;
}
for ( int i = 2 ; i < MAX ; i++ ) {
if ( primes[i] ) {
for ( int j = 2*i ; j < MAX ; j += i ) {
primes[j] = false;
}
}
}
}
 
// See http://primes.utm.edu/glossary/page.php?sort=StrongPRP
public static final boolean isPrime(long testValue) {
if ( testValue == 2 ) return true;
if ( testValue % 2 == 0 ) return false;
if ( testValue <= MAX ) return isPrimeTrivial(testValue);
long d = testValue-1;
int s = 0;
while ( d % 2 == 0 ) {
s += 1;
d /= 2;
}
if ( testValue < 1373565L ) {
if ( ! aSrp(2, s, d, testValue) ) {
return false;
}
if ( ! aSrp(3, s, d, testValue) ) {
return false;
}
return true;
}
if ( testValue < 4759123141L ) {
if ( ! aSrp(2, s, d, testValue) ) {
return false;
}
if ( ! aSrp(7, s, d, testValue) ) {
return false;
}
if ( ! aSrp(61, s, d, testValue) ) {
return false;
}
return true;
}
if ( testValue < 10000000000000000L ) {
if ( ! aSrp(3, s, d, testValue) ) {
return false;
}
if ( ! aSrp(24251, s, d, testValue) ) {
return false;
}
return true;
}
// Try 5 "random" primes
if ( ! aSrp(37, s, d, testValue) ) {
return false;
}
if ( ! aSrp(47, s, d, testValue) ) {
return false;
}
if ( ! aSrp(61, s, d, testValue) ) {
return false;
}
if ( ! aSrp(73, s, d, testValue) ) {
return false;
}
if ( ! aSrp(83, s, d, testValue) ) {
return false;
}
//throw new RuntimeException("ERROR isPrime: Value too large = "+testValue);
return true;
}
 
private static final boolean aSrp(int a, int s, long d, long n) {
long modPow = modPow(a, d, n);
//System.out.println("a = "+a+", s = "+s+", d = "+d+", n = "+n+", modpow = "+modPow);
if ( modPow == 1 ) {
return true;
}
int twoExpR = 1;
for ( int r = 0 ; r < s ; r++ ) {
if ( modPow(modPow, twoExpR, n) == n-1 ) {
return true;
}
twoExpR *= 2;
}
return false;
}
private static final long SQRT = (long) Math.sqrt(Long.MAX_VALUE);
public static final long modPow(long base, long exponent, long modulus) {
long result = 1;
while ( exponent > 0 ) {
if ( exponent % 2 == 1 ) {
if ( result > SQRT || base > SQRT ) {
result = multiply(result, base, modulus);
}
else {
result = (result * base) % modulus;
}
}
exponent >>= 1;
if ( base > SQRT ) {
base = multiply(base, base, modulus);
}
else {
base = (base * base) % modulus;
}
}
return result;
}
 
 
// Result is a*b % mod, without overflow.
public static final long multiply(long a, long b, long modulus) {
long x = 0;
long y = a % modulus;
long t;
while ( b > 0 ) {
if ( b % 2 == 1 ) {
t = x + y;
x = (t > modulus ? t-modulus : t);
}
t = y << 1;
y = (t > modulus ? t-modulus : t);
b >>= 1;
}
return x % modulus;
}
 
}
</syntaxhighlight>
{{out}}
<pre>
U(3, 1) = 7 * 13 * 19 = 1729
U(4, 1) = 7 * 13 * 19 * 37 = 63973
U(5, 380) = 2281 * 4561 * 6841 * 13681 * 27361 = 26641259752490421121
U(6, 380) = 2281 * 4561 * 6841 * 13681 * 27361 * 54721 = 1457836374916028334162241
U(7, 780320) = 4681921 * 9363841 * 14045761 * 28091521 * 56183041 * 112366081 * 224732161 = 24541683183872873851606952966798288052977151461406721
U(8, 950560) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 = 53487697914261966820654105730041031613370337776541835775672321
U(9, 950560) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121 = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Primes
 
function trial_pretest(k::UInt64)
 
if ((k % 3)==0 || (k % 5)==0 || (k % 7)==0 || (k % 11)==0 ||
(k % 13)==0 || (k % 17)==0 || (k % 19)==0 || (k % 23)==0)
return (k <= 23)
end
 
return true
end
 
function gcd_pretest(k::UInt64)
 
if (k <= 107)
return true
end
 
gcd(29*31*37*41*43*47*53*59*61*67, k) == 1 &&
gcd(71*73*79*83*89*97*101*103*107, k) == 1
end
 
function is_chernick(n::Int64, m::UInt64)
 
t = 9*m
 
if (!trial_pretest(6*m + 1))
return false
end
 
if (!trial_pretest(12*m + 1))
return false
end
 
for i in 1:n-2
if (!trial_pretest((t << i) + 1))
return false
end
end
 
if (!gcd_pretest(6*m + 1))
return false
end
 
if (!gcd_pretest(12*m + 1))
return false
end
 
for i in 1:n-2
if (!gcd_pretest((t << i) + 1))
return false
end
end
 
if (!isprime(6*m + 1))
return false
end
 
if (!isprime(12*m + 1))
return false
end
 
for i in 1:n-2
if (!isprime((t << i) + 1))
return false
end
end
 
return true
end
 
function chernick_carmichael(n::Int64, m::UInt64)
prod = big(1)
 
prod *= 6*m + 1
prod *= 12*m + 1
 
for i in 1:n-2
prod *= ((big(9)*m)<<i) + 1
end
 
prod
end
 
function cc_numbers(from, to)
 
for n in from:to
 
multiplier = 1
 
if (n > 4) multiplier = 1 << (n-4) end
if (n > 5) multiplier *= 5 end
 
m = UInt64(multiplier)
 
while true
 
if (is_chernick(n, m))
println("a(", n, ") = ", chernick_carmichael(n, m))
break
end
 
m += multiplier
end
end
end
 
cc_numbers(3, 10)</syntaxhighlight>
 
{{out}}
<pre>
a(3) = 1729
a(4) = 63973
a(5) = 26641259752490421121
a(6) = 1457836374916028334162241
a(7) = 24541683183872873851606952966798288052977151461406721
a(8) = 53487697914261966820654105730041031613370337776541835775672321
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
a(10) = 24616075028246330441656912428380582403261346369700917629170235674289719437963233744091978433592331048416482649086961226304033068172880278517841921
</pre>
 
(takes ~6.5 minutes)
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[PrimeFactorCounts, U]
PrimeFactorCounts[n_Integer] := Total[FactorInteger[n][[All, 2]]]
U[n_, m_] := (6 m + 1) (12 m + 1) Product[2^i 9 m + 1, {i, 1, n - 2}]
FindFirstChernickCarmichaelNumber[n_Integer?Positive] :=
Module[{step, i, m, formula, value},
step = Ceiling[2^(n - 4)];
If[n > 5, step *= 5];
i = step;
formula = U[n, m];
PrintTemporary[Dynamic[i]];
While[True,
value = formula /. m -> i;
If[PrimeFactorCounts[value] == n,
Break[];
];
i += step
];
{i, value}
]
FindFirstChernickCarmichaelNumber[3]
FindFirstChernickCarmichaelNumber[4]
FindFirstChernickCarmichaelNumber[5]
FindFirstChernickCarmichaelNumber[6]
FindFirstChernickCarmichaelNumber[7]
FindFirstChernickCarmichaelNumber[8]
FindFirstChernickCarmichaelNumber[9]</syntaxhighlight>
{{out}}
<pre>{1,1729}
{1,63973}
{380,26641259752490421121}
{380,1457836374916028334162241}
{780320,24541683183872873851606952966798288052977151461406721}
{950560,53487697914261966820654105730041031613370337776541835775672321}
{950560,58571442634534443082821160508299574798027946748324125518533225605795841}</pre>
=={{header|Nim}}==
{{libheader|bignum}}
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 tested number 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.
 
<syntaxhighlight 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'</syntaxhighlight>
 
{{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}}==
<syntaxhighlight lang="parigp">
cherCar(n)={
my(C=vector(n));C[1]=6; C[2]=12; for(g=3,n,C[g]=2^(g-2)*9);
my(i=1); my(N(g)=while(i<=n&ispseudoprime(g*C[i]+1),i=i+1); return(i>n));
i=1; my(G(g)=while(i<=n&isprime(g*C[i]+1),i=i+1); return(i>n));
i=1; if(n>4,i=2^(n-4)); if(n>5,i=i*5); my(m=i); while(!(N(m)&G(m)),m=m+i);
printf("cherCar(%d): m = %d\n",n,m)}
for(x=3,9,cherCar(x))
</syntaxhighlight>
{{out}}
<pre>
cherCar(3): m = 1
cherCar(4): m = 1
cherCar(5): m = 380
cherCar(6): m = 380
cherCar(7): m = 780320
cherCar(8): m = 950560
cherCar(9): m = 950560
cherCar(10): m = 3208386195840
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use 5.020;
use warnings;
use ntheory qw/:all/;
Line 164 ⟶ 1,029:
foreach my $n (3..9) {
chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) });
}</langsyntaxhighlight>
 
{{out}}
Line 176 ⟶ 1,041:
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
=={{header|Phix}}==
{{libheader|Phix/mpfr}}
{{trans|Sidef}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">chernick_carmichael_factors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">m_prime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_d</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">is_chernick_carmichael</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">==</span><span style="color: #000000;">2</span> <span style="color: #0000FF;">?</span> <span style="color: #000000;">m_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">6</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">m_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">:</span> <span style="color: #000000;">m_prime</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span>
<span style="color: #000000;">is_chernick_carmichael</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">chernick_carmichael_number</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">4</span> <span style="color: #0000FF;">?</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">:</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">mm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span>
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">is_chernick_carmichael</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">mm</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">m</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">chernick_carmichael_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mm</span><span style="color: #0000FF;">),</span><span style="color: #000000;">mm</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chernick_carmichael_number</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul_d</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"U(%d,%d): %s = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" * "</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre style="font-size: 10px">
U(3,1): 1729 = 7 * 13 * 19
U(4,1): 63973 = 7 * 13 * 19 * 37
U(5,380): 26641259752490421121 = 2281 * 4561 * 6841 * 13681 * 27361
U(6,380): 1457836374916028334162241 = 2281 * 4561 * 6841 * 13681 * 27361 * 54721
U(7,780320): 24541683183872873851606952966798288052977151461406721 = 4681921 * 9363841 * 14045761 * 28091521 * 56183041 * 112366081 * 224732161
U(8,950560): 53487697914261966820654105730041031613370337776541835775672321 = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561
U(9,950560): 58571442634534443082821160508299574798027946748324125518533225605795841 = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121
</pre>
Pleasingly fast, note however that a(10) remains well out of reach / would probably need a complete rewrite.
 
=== with cheat ===
=={{header|Perl 6}}==
{{trans|C}} with added cheat for the a(10) case - I found a nice big prime factor of k and added that on each iteration instead of 1.<br>
{{works with|Rakudo|2019.03}}
You could also use the sequence {1,1,1,1,19,19,4877,457,457,12564169}, if you know a way to build that, and then it wouldn't be cheating anymore...
{{trans|Perl}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
Use the ntheory library from Perl 5 for primality testing since it is much, ''much'' faster than Perl 6s built-in .is-prime method.
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ppp</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">primality_pretest</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ppp</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ppp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">23</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">probprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_d</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">is_chernick</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primality_pretest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">6</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primality_pretest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primality_pretest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">probprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">6</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">probprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">probprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">multiplier</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">4</span> <span style="color: #0000FF;">?</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">:</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">multiplier</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">5</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">10</span> <span style="color: #008080;">then</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">12564168</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- cheat!</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">multiplier</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">is_chernick</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"a(%d) has m = %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{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
a(10) has m = 3208386195840
"0.1s"
</pre>
=={{header|Prolog}}==
SWI Prolog is too slow to solve for a(10), even with optimizing by increasing the multiplier and implementing a trial division check. (actually, my implementation of Miller-Rabin in Prolog already starts with a trial division by small primes.)
<syntaxhighlight lang="prolog">
?- use_module(library(primality)).
 
u(3, M, A * B * C) :-
<lang perl6>use Inline::Perl5;
A is 6*M + 1, B is 12*M + 1, C is 18*M + 1, !.
u(N, M, U0 * D) :-
succ(Pn, N), u(Pn, M, U0),
D is 9*(1 << (N - 2))*M + 1.
 
prime_factorization(A*B) :- prime(B), prime_factorization(A), !.
prime_factorization(A) :- prime(A).
 
step(N, 1) :- N < 5, !.
step(5, 2) :- !.
step(N, K) :- K is 5*(1 << (N - 4)).
 
a(N, Factors) :- % due to backtracking nature of Prolog, a(n) will return all chernick-carmichael numbers.
N > 2, !,
step(N, I),
between(1, infinite, J), M is I * J,
u(N, M, Factors),
prime_factorization(Factors).
 
main :-
forall(
(between(3, 9, K), once(a(K, Factorization)), N is Factorization),
format("~w: ~w = ~w~n", [K, Factorization, N])),
halt.
 
?- main.
</syntaxhighlight>
isprime predicate:
<syntaxhighlight lang="prolog">
prime(N) :-
integer(N),
N > 1,
divcheck(
N,
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
139, 149],
Result),
((Result = prime, !); miller_rabin_primality_test(N)).
 
divcheck(_, [], unknown) :- !.
divcheck(N, [P|_], prime) :- P*P > N, !.
divcheck(N, [P|Ps], State) :- N mod P =\= 0, divcheck(N, Ps, State).
 
miller_rabin_primality_test(N) :-
bases(Bases, N),
forall(member(A, Bases), strong_fermat_pseudoprime(N, A)).
 
miller_rabin_precision(16).
 
bases([31, 73], N) :- N < 9_080_191, !.
bases([2, 7, 61], N) :- N < 4_759_123_141, !.
bases([2, 325, 9_375, 28_178, 450_775, 9_780_504, 1_795_265_022], N) :-
N < 18_446_744_073_709_551_616, !. % 2^64
bases(Bases, N) :-
miller_rabin_precision(T), RndLimit is N - 2,
length(Bases, T), maplist(random_between(2, RndLimit), Bases).
 
strong_fermat_pseudoprime(N, A) :- % miller-rabin strong pseudoprime test with base A.
succ(Pn, N), factor_2s(Pn, S, D),
X is powm(A, D, N),
((X =:= 1, !); \+ composite_witness(N, S, X)).
 
composite_witness(_, 0, _) :- !.
composite_witness(N, K, X) :-
X =\= N-1,
succ(Pk, K), X2 is (X*X) mod N, composite_witness(N, Pk, X2).
 
factor_2s(N, S, D) :- factor_2s(0, N, S, D).
factor_2s(S, D, S, D) :- D /\ 1 =\= 0, !.
factor_2s(S0, D0, S, D) :-
succ(S0, S1), D1 is D0 >> 1,
factor_2s(S1, D1, S, D).
</syntaxhighlight>
{{Out}}
<pre>
3: 7*13*19 = 1729
4: 7*13*19*37 = 63973
5: 2281*4561*6841*13681*27361 = 26641259752490421121
6: 2281*4561*6841*13681*27361*54721 = 1457836374916028334162241
7: 4681921*9363841*14045761*28091521*56183041*112366081*224732161 = 24541683183872873851606952966798288052977151461406721
8: 5703361*11406721*17110081*34220161*68440321*136880641*273761281*547522561 = 53487697914261966820654105730041031613370337776541835775672321
9: 5703361*11406721*17110081*34220161*68440321*136880641*273761281*547522561*1095045121 = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
=={{header|Python}}==
<syntaxhighlight 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
</syntaxhighlight>
 
{{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)
 
Use the ntheory library from Perl for primality testing since it is much, ''much'' faster than Raku's built-in .is-prime method.
{{trans|Perl}}
{{libheader|ntheory}}
<syntaxhighlight lang="raku" line>use Inline::Perl5;
use ntheory:from<Perl5> <:all>;
 
sub chernick-carmichael-factors ($n, $m) {
6*6×$m + 1, 12*12×$m + 1, |((1 .. $n-2).map: { (1 +< $_) *× 9*9×$m + 1 } )
}
 
sub chernick-carmichael-number ($n) {
 
my $multiplier = 1 +< (($n-4) max 0);
my $iterator = $n < 5 ?? (1 .. *) !! (1 .. *).map: * × 5;
 
if$multiplier × $niterator.first: -> 4$m {
[&&] chernick-factors($n, $m × $multiplier).map: { is_prime($_) }
$multiplier = 1 +< ($n-4);
$iterator = (1..*).map: * * 5;
}
 
my $i = $iterator.first: -> $m {
[&&] chernick-carmichael-factors($n, $m * $multiplier).map: { is_prime($_) #`[ .is-prime ] }
}
 
chernick-carmichael-factors($n, $i * $multiplier)
 
}
 
for 3 .. 9 -> $n {
my @f$m = chernick-carmichael-number($n);
say "a($n): {[*]my @f} = {@f.joinchernick-factors('$n, ⨉ '$m)}";
say "U($n, $m): {[×] @f} = {@f.join(' ⨉ ')}";
}</lang>
}</syntaxhighlight>
{{out}}
<pre>aU(3, 1): 1729 = 7 ⨉ 13 ⨉ 19
aU(4, 1): 63973 = 7 ⨉ 13 ⨉ 19 ⨉ 37
aU(5, 380): 26641259752490421121 = 2281 ⨉ 4561 ⨉ 6841 ⨉ 13681 ⨉ 27361
aU(6, 380): 1457836374916028334162241 = 2281 ⨉ 4561 ⨉ 6841 ⨉ 13681 ⨉ 27361 ⨉ 54721
aU(7, 780320): 24541683183872873851606952966798288052977151461406721 = 4681921 ⨉ 9363841 ⨉ 14045761 ⨉ 28091521 ⨉ 56183041 ⨉ 112366081 ⨉ 224732161
aU(8, 950560): 53487697914261966820654105730041031613370337776541835775672321 = 5703361 ⨉ 11406721 ⨉ 17110081 ⨉ 34220161 ⨉ 68440321 ⨉ 136880641 ⨉ 273761281 ⨉ 547522561
aU(9, 950560): 58571442634534443082821160508299574798027946748324125518533225605795841 = 5703361 ⨉ 11406721 ⨉ 17110081 ⨉ 34220161 ⨉ 68440321 ⨉ 136880641 ⨉ 273761281 ⨉ 547522561 ⨉ 1095045121</pre>
</pre>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func chernick_carmichael_factors (n, m) {
[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...]
}
Line 240 ⟶ 1,391:
for n in (3..9) {
chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" })
}</langsyntaxhighlight>
 
{{out}}
Line 251 ⟶ 1,402:
a(8) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561
a(9) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121
</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
Based on Go's 'more efficient' version. Reaches a(9) in just over 0.1 seconds but a(10) would still be out of reasonable reach for Wren so I've had to be content with that.
<syntaxhighlight lang="wren">import "./big" for BigInt, BigInts
import "./fmt" for Fmt
 
var min = 3
var max = 9
var prod = BigInt.zero
var fact = BigInt.zero
var factors = List.filled(max, 0)
var bigFactors = List.filled(max, null)
 
var init = Fn.new {
for (i in 0...max) bigFactors[i] = BigInt.zero
}
 
var isPrimePretest = Fn.new { |k|
if (k%3 == 0 || k%5 == 0 || k%7 == 0 || k%11 == 0 ||
(k%13 == 0) || k%17 == 0 || k%19 == 0 || k%23 == 0) return k <= 23
return true
}
 
var ccFactors = Fn.new { |n, m|
if (!isPrimePretest.call(6*m + 1)) return false
if (!isPrimePretest.call(12*m + 1)) return false
factors[0] = 6*m + 1
factors[1] = 12*m + 1
var t = 9 * m
var i = 1
while (i <= n-2) {
var tt = (t << i) + 1
if (!isPrimePretest.call(tt)) return false
factors[i+1] = tt
i = i + 1
}
for (i in 0...n) {
fact = BigInt.new(factors[i])
if (!fact.isProbablePrime(1)) return false
bigFactors[i] = fact
}
return true
}
 
var ccNumbers = Fn.new { |start, end|
for (n in start..end) {
var mult = 1
if (n > 4) mult = 1 << (n - 4)
if (n > 5) mult = mult * 5
var m = mult
while (true) {
if (ccFactors.call(n, m)) {
var num = BigInts.prod(bigFactors.take(n))
Fmt.print("a($d) = $i", n, num)
Fmt.print("m($d) = $d", n, m)
Fmt.print("Factors: $n\n", factors[0...n])
break
}
m = m + mult
}
}
}
 
init.call()
ccNumbers.call(min, max)</syntaxhighlight>
 
{{out}}
<pre>
a(3) = 1729
m(3) = 1
Factors: [7, 13, 19]
 
a(4) = 63973
m(4) = 1
Factors: [7, 13, 19, 37]
 
a(5) = 26641259752490421121
m(5) = 380
Factors: [2281, 4561, 6841, 13681, 27361]
 
a(6) = 1457836374916028334162241
m(6) = 380
Factors: [2281, 4561, 6841, 13681, 27361, 54721]
 
a(7) = 24541683183872873851606952966798288052977151461406721
m(7) = 780320
Factors: [4681921, 9363841, 14045761, 28091521, 56183041, 112366081, 224732161]
 
a(8) = 53487697914261966820654105730041031613370337776541835775672321
m(8) = 950560
Factors: [5703361, 11406721, 17110081, 34220161, 68440321, 136880641, 273761281, 547522561]
 
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
m(9) = 950560
Factors: [5703361, 11406721, 17110081, 34220161, 68440321, 136880641, 273761281, 547522561, 1095045121]
</pre>
 
Line 258 ⟶ 1,507:
Using GMP (probabilistic primes),
because it is easy and fast to check primeness.
<langsyntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP
 
fcn ccFactors(n,m){ // not re-entrant
Line 285 ⟶ 1,534:
}
}
}</langsyntaxhighlight>
<syntaxhighlight lang ="zkl">ccNumbers(3,9);</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/290905...353826"