Chernick's Carmichael numbers
In 1939, Jack Chernick proved that, for n ≥ 3 and m ≥ 1:
U(n, m) = (6m + 1) * (12m + 1) * Product_{i=1..n-2} (2^i * 9m + 1)
is a Carmichael number if all the factors are primes and, for n > 4, m is a multiple of 2^(n-4).
- Example
U(3, m) = (6m + 1) * (12m + 1) * (18m + 1) U(4, m) = U(3, m) * (2^2 * 9m + 1) U(5, m) = U(4, m) * (2^3 * 9m + 1) ... U(n, m) = U(n-1, m) * (2^(n-2) * 9m + 1)
- The smallest Chernick's Carmichael number with 3 prime factors, is: U(3, 1) = 1729.
- The smallest Chernick's Carmichael number with 4 prime factors, is: U(4, 1) = 63973.
- The smallest Chernick's Carmichael number with 5 prime factors, is: U(5, 380) = 26641259752490421121.
For n = 5, the smallest number m that satisfy Chernick's conditions, is m = 380, therefore U(5, 380) is the smallest Chernick's Carmichael number with 5 prime factors.
U(5, 380) is a Chernick's Carmichael number because m = 380 is a multiple of 2^(n-4), where n = 5, and the factors { (6*380 + 1), (12*380 + 1), (18*380 + 1), (36*380 + 1), (72*380 + 1) } are all prime numbers.
- Task
For n ≥ 3, let a(n) be the smallest Chernick's Carmichael number with n prime factors.
- Compute a(n) for n = 3..9.
- Optional: try to find a(10). (this may take a long time)
Note: it's perfectly acceptable to show the terms in factorized form:
a(3) = 7 * 13 * 19 a(4) = 7 * 13 * 19 * 37 a(5) = 2281 * 4561 * 6841 * 13681 * 27361 ...
- See also
Perl
<lang perl>use 5.020; use warnings; use ntheory qw/:all/; use experimental qw/signatures/;
sub chernick_carmichael_factors ($n, $m) {
(6*$m + 1, 12*$m + 1, (map { (1 << $_) * 9*$m + 1 } 1 .. $n-2));
}
sub chernick_carmichael_number ($n, $callback) {
my $multiplier = ($n > 4) ? (1 << ($n-4)) : 1;
for (my $m = 1 ; ; ++$m) { my @f = chernick_carmichael_factors($n, $m * $multiplier); next if not vecall { is_prime($_) } @f; $callback->(@f); last; }
}
foreach my $n (3..9) {
chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) });
}</lang>
- Output:
a(3) = 1729 a(4) = 63973 a(5) = 26641259752490421121 a(6) = 1457836374916028334162241 a(7) = 24541683183872873851606952966798288052977151461406721 a(8) = 53487697914261966820654105730041031613370337776541835775672321 a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
Perl 6
Use the ntheory library from Perl 5 for primality testing since it is much, much faster than Perl 6s built-in .is-prime method.
<lang perl6>use Inline::Perl5; use ntheory:from<Perl5> <:all>;
sub chernick-carmichael-factors ($n, $m) {
6*$m + 1, 12*$m + 1, |((1 .. $n-2).map: { (1 +< $_) * 9*$m + 1 } )
}
sub chernick-carmichael-number ($n) {
my $multiplier = 1; my $iterator = 1 .. *;
if $n > 4 { $multiplier = 1 +< ($n-4); $iterator = (1..*).map: * * 5; }
my $i = $iterator.first: -> $m { next unless [&&] chernick-carmichael-factors($n, $m * $multiplier).map: { is_prime($_) #`[ .is-prime ] }; last } chernick-carmichael-factors($n, $i * $multiplier);
}
for 3 .. 9 -> $n {
my @f = chernick-carmichael-number($n); say "a($n): {[*] @f} = {@f.join(' ⨉ ')}";
}</lang>
- Output:
a(3): 1729 = 7 ⨉ 13 ⨉ 19 a(4): 63973 = 7 ⨉ 13 ⨉ 19 ⨉ 37 a(5): 26641259752490421121 = 2281 ⨉ 4561 ⨉ 6841 ⨉ 13681 ⨉ 27361 a(6): 1457836374916028334162241 = 2281 ⨉ 4561 ⨉ 6841 ⨉ 13681 ⨉ 27361 ⨉ 54721 a(7): 24541683183872873851606952966798288052977151461406721 = 4681921 ⨉ 9363841 ⨉ 14045761 ⨉ 28091521 ⨉ 56183041 ⨉ 112366081 ⨉ 224732161 a(8): 53487697914261966820654105730041031613370337776541835775672321 = 5703361 ⨉ 11406721 ⨉ 17110081 ⨉ 34220161 ⨉ 68440321 ⨉ 136880641 ⨉ 273761281 ⨉ 547522561 a(9): 58571442634534443082821160508299574798027946748324125518533225605795841 = 5703361 ⨉ 11406721 ⨉ 17110081 ⨉ 34220161 ⨉ 68440321 ⨉ 136880641 ⨉ 273761281 ⨉ 547522561 ⨉ 1095045121
Sidef
<lang ruby>func chernick_carmichael_factors (n, m) {
[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...]
}
func is_chernick_carmichael (n, m) {
(n == 2) ? (is_prime(6*m + 1) && is_prime(12*m + 1)) : (is_prime(2**(n-2) * 9*m + 1) && __FUNC__(n-1, m))
}
func chernick_carmichael_number(n, callback) {
var multiplier = (n>4 ? 2**(n-4) : 1) var m = (1..Inf -> first {|m| is_chernick_carmichael(n, m * multiplier) }) var f = chernick_carmichael_factors(n, m * multiplier) callback(f...)
}
for n in (3..9) {
chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" })
}</lang>
- Output:
a(3) = 7 * 13 * 19 a(4) = 7 * 13 * 19 * 37 a(5) = 2281 * 4561 * 6841 * 13681 * 27361 a(6) = 2281 * 4561 * 6841 * 13681 * 27361 * 54721 a(7) = 4681921 * 9363841 * 14045761 * 28091521 * 56183041 * 112366081 * 224732161 a(8) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 a(9) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121