Chernick's Carmichael numbers

Chernick's Carmichael numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

• Jack Chernick, On Fermat's simple theorem (PDF)

• OEIS A318646: The least Chernick's "universal form" Carmichael number with n prime factors

Perl

Library: ntheory

<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

Works with: Rakudo version 2019.03

Translation of: Perl

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