Chernick's Carmichael numbers: Difference between revisions

 

<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|FreeBASIC}}==

===Basic only===

 

Function PrimalityPretest(k As Integer) As Boolean

Loop

Next n

=={{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|J}}==

 

Brute force:

 

if.3=y do.1729 return.end.

m=. z=. 2^y-4

m=.m+z

end.

 

Task examples:

 

1729

a 4

53487697914261966820654105730041031613370337776541835775672321

a 9

=={{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|Mathematica}} / {{header|Wolfram Language}}==

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[7]

FindFirstChernickCarmichaelNumber[8]

{{out}}

<pre>{1,1729}

{950560,53487697914261966820654105730041031613370337776541835775672321}

{950560,58571442634534443082821160508299574798027946748324125518533225605795841}</pre>

=={{header|Nim}}==

{{libheader|bignum}}

With these optimizations, the program executes in 4-5 minutes.

 

import bignum

 

s.addSep(" × ")

s.add($factor)

 

{{out}}

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}}==

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

<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: #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>

{{out}}

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

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

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

<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: #008080;">end</span> <span style="color: #008080;">procedure</span>

<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

"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.)

?- use_module(library(primality)).

 

 

?- main.

isprime predicate:

prime(N) :-

integer(N),

succ(S0, S1), D1 is D0 >> 1,

factor_2s(S1, D1, S, D).

{{Out}}

<pre>

</pre>

=={{header|Python}}==

"""

 

k += 1

 

{{out}}

a(9) has m = 950560

</pre>

=={{header|Raku}}==

(formerly Perl 6)

{{trans|Perl}}

{{libheader|ntheory}}

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

 

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

say "U($n, $m): {[×] @f} = {@f.join(' ⨉ ')}";

{{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(9) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121

</pre>

=={{header|Wren}}==

{{trans|Go}}

{{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.

 

var min = 3

 

init.call()

 

{{out}}

Using GMP (probabilistic primes),

because it is easy and fast to check primeness.

 

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

}

}

{{out}}

<pre>