Chernick's Carmichael numbers: Difference between revisions

{{task|Mathematics}}

In 1939, Jack Chernick proved that, for '''n ≥ 3''' and '''m ≥ 1''':

 

 

<br><br>

=={{header|C}}==

{{libheader|GMP}}

#include <stdlib.h>

#include <gmp.h>

 

return 0;

{{out}}

<pre>

a(10) has m = 3208386195840

</pre>

=={{header|C++}}==

{{libheader|GMP}}

#include <iostream>

 

 

return 0;

{{out}}

<pre>

</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#)]

// Generate Chernick's Carmichael numbers. Nigel Galloway: June 1st., 2019

let fMk m k=isPrime(6*m+1) && isPrime(12*m+1) && [1..k-2]|>List.forall(fun n->isPrime(9*(pown 2 n)*m+1))

let cherCar k=let m=Seq.head(fX k) in printfn "m=%d primes -> %A " m ([6*m+1;12*m+1]@List.init(k-2)(fun n->9*(pown 2 (n+1))*m+1))

[4..9] |> Seq.iter cherCar

{{out}}

<pre>

cherCar(9): m=950560 primes -> [5703361; 11406721; 17110081; 34220161; 68440321; 136880641; 273761281; 547522561; 1095045121]

</pre>

 

=={{header|Go}}==

===Basic only===

 

import (

func main() {

ccNumbers(3, 9)

 

{{out}}

 

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.

 

import (

func main() {

ccNumbers(min, max)

 

{{out}}

Factors: [19250317175041 38500634350081 57750951525121 115501903050241 231003806100481 462007612200961 924015224401921 1848030448803841 3696060897607681 7392121795215361]

</pre>

 

=={{header|Java}}==

import java.math.BigInteger;

import java.util.ArrayList;

 

}

{{out}}

<pre>

U(9, 950560) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121 = 58571442634534443082821160508299574798027946748324125518533225605795841

</pre>

=={{header|Julia}}==

 

function trial_pretest(k::UInt64)

end

 

 

{{out}}

 

(takes ~6.5 minutes)

 

=={{header|PARI/GP}}==

cherCar(n)={

my(C=vector(n));C[1]=6; C[2]=12; for(g=3,n,C[g]=2^(g-2)*9);

printf("cherCar(%d): m = %d\n",n,m)}

for(x=3,9,cherCar(x))

{{out}}

<pre>

cherCar(10): m = 3208386195840

</pre>

=={{header|Perl}}==

{{libheader|ntheory}}

use warnings;

use ntheory qw/:all/;

foreach my $n (3..9) {

chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) });

 

{{out}}

a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841

</pre>

=={{header|Phix}}==

{{libheader|Phix/mpfr}}

{{trans|Sidef}}

{{out}}

<pre style="font-size: 10px">

 

=== with cheat ===

{{out}}

<pre>

"0.1s"

</pre>

 

=={{header|Raku}}==

(formerly Perl 6)

 

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

 

sub chernick-factors ($n, $m) {

}

 

 

my $multiplier = 1 +< (($n-4) max 0);

 

}

 

my $m = chernick-carmichael-number($n);

my @f = chernick-factors($n, $m);

{{out}}

<pre>U(3, 1): 1729 = 7 ⨉ 13 ⨉ 19

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>

=={{header|Sidef}}==

[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...]

}

for n in (3..9) {

chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" })

 

{{out}}

a(8) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561

a(9) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121

</pre>

 

Using GMP (probabilistic primes),

because it is easy and fast to check primeness.

 

fcn ccFactors(n,m){ // not re-entrant

}

}

{{out}}

<pre>