user
In 1939, Jack Chernick proved that, for **n
≥
3
{\displaystyle {\displaystyle n\geq 3}}** and **m
≥
1
{\displaystyle {\displaystyle m\geq 1}}**:

```
   
  
    
      
        
          
            U
            (
            n
            ,
            m
            )
            =
            (
            6
            m
            +
            1
            )
            (
            12
            m
            +
            1
            )
            
              ∏
              
                k
                =
                1
              
              
                n
                −
                2
              
            
            (
            
              2
              
                k
              
            
            
            9
            m
            +
            1
            )
          
        
      
    
    {\displaystyle {\displaystyle U(n,m)=(6m+1)(12m+1)\prod _{k=1}^{n-2}(2^{k}\,9m+1)}}
  


```

is a Carmichael number if all the factors are primes and, for **n
>
4
{\displaystyle {\displaystyle n>4}}**, **m
{\displaystyle {\displaystyle m}}** is a multiple of **2

(
n
−
4
)
{\displaystyle {\displaystyle 2^{(n-4)}}}**.

Example

```
   
  
    
      
        
          
            U
            (
            3
            ,
            m
            )
            =
            (
            6
            m
            +
            1
            )
            (
            12
            m
            +
            1
            )
            (
            18
            m
            +
            1
            )
          
        
      
    
    {\displaystyle {\displaystyle U(3,m)=(6m+1)(12m+1)(18m+1)}}
  

   
  
    
      
        
          
            U
            (
            4
            ,
            m
            )
            =
            U
            (
            3
            ,
            m
            )
            (
            
              2
              
                2
              
            
            9
            m
            +
            1
            )
          
        
      
    
    {\displaystyle {\displaystyle U(4,m)=U(3,m)(2^{2}9m+1)}}
  

   
  
    
      
        
          
            U
            (
            5
            ,
            m
            )
            =
            U
            (
            4
            ,
            m
            )
            (
            
              2
              
                3
              
            
            9
            m
            +
            1
            )
          
        
      
    
    {\displaystyle {\displaystyle U(5,m)=U(4,m)(2^{3}9m+1)}}
  

   
  
    
      
        
          
            ⋯
          
        
      
    
    {\displaystyle {\displaystyle \cdots }}
  

   
  
    
      
        
          
            U
            (
            n
            ,
            m
            )
            =
            U
            (
            n
            −
            1
            ,
            m
            )
            (
            
              2
              
                (
                n
                −
                2
                )
              
            
            9
            m
            +
            1
            )
          
        
      
    
    {\displaystyle {\displaystyle 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: find **a(10)**.

**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), equation (8)

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

Related tasks

* Carmichael 3 strong pseudoprimes
assistant
(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.

**Translation of**: Perl

**Library:** ntheory

```
use Inline::Perl5;
use ntheory:from<Perl5> <:all>;

sub chernick-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 +< (($n-4) max 0);
    my $iterator   = $n < 5 ?? (1 .. *) !! (1 .. *).map: * × 5;

    $multiplier × $iterator.first: -> $m {
        [&&] chernick-factors($n, $m × $multiplier).map: { is_prime($_) }
    }

}

for 3 .. 9 -> $n {
    my $m = chernick-carmichael-number($n);
    my @f = chernick-factors($n, $m);
    say "U($n, $m): {[×] @f} = {@f.join(' ⨉ ')}";
}

```

Output:

```
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
```