Rosetta Code

Chernick's Carmichael numbers: Difference between revisions

Page Discussion

Chernick's Carmichael numbers (view source)

Revision as of 12:26, 17 November 2023

2,457 bytes added ,  6 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Phix}}: added syntax colouring the hard way)
m (→‎{{header|Wren}}: Minor tidy)
 
(7 intermediate revisions by 5 users not shown)
Line 1:
{{task|Mathematics}}
[[category:Prime Numbers]]
In 1939, Jack Chernick proved that, for '''n ≥ 3''' and '''m ≥ 1''':
 
Line 52 ⟶ 53:
 
<br><br>
 
=={{header|C}}==
{{libheader|GMP}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
Line 105:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 117:
a(10) has m = 3208386195840
</pre>
 
=={{header|C++}}==
{{libheader|GMP}}
<langsyntaxhighlight lang="cpp">#include <gmp.h>
#include <iostream>
 
Line 205 ⟶ 204:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 218 ⟶ 217:
</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#)]
<langsyntaxhighlight lang="fsharp">
// 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))
Line 227 ⟶ 225:
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
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 237 ⟶ 235:
cherCar(9): m=950560 primes -> [5703361; 11406721; 17110081; 34220161; 68440321; 136880641; 273761281; 547522561; 1095045121]
</pre>
=={{header|FreeBASIC}}==
===Basic only===
<syntaxhighlight lang="freebasic">#include "isprime.bas"
 
Function PrimalityPretest(k As Integer) As Boolean
Dim As Integer ppp(1 To 8) = {3,5,7,11,13,17,19,23}
For i As Integer = 1 To Ubound(ppp)
If k Mod ppp(i) = 0 Then Return (k <= 23)
Next i
Return True
End Function
 
Function isChernick(n As Integer, m As Integer) As Boolean
Dim As Integer i, t = 9 * m
If Not PrimalityPretest(6 * m + 1) Then Return False
If Not PrimalityPretest(12 * m + 1) Then Return False
For i = 1 To n-1
If Not PrimalityPretest(t * (2 ^ i) + 1) Then Return False
Next i
If Not isPrime(6 * m + 1) Then Return False
If Not isPrime(12 * m + 1) Then Return False
For i = 1 To n - 2
If Not isPrime(t * (2 ^ i) + 1) Then Return False
Next i
Return True
End Function
 
Dim As Uinteger multiplier, k, m = 1
For n As Integer = 3 To 9
multiplier = Iif (n > 4, 2 ^ (n-4), 1)
If n > 5 Then multiplier *= 5
k = 1
Do
m = k * multiplier
If isChernick(n, m) Then
Print "a(" & n & ") has m = " & m
Exit Do
End If
k += 1
Loop
Next n
Sleep</syntaxhighlight>
=={{header|Go}}==
===Basic only===
<langsyntaxhighlight lang="go">package main
 
import (
Line 296 ⟶ 340:
func main() {
ccNumbers(3, 9)
}</langsyntaxhighlight>
 
{{out}}
Line 318 ⟶ 362:
 
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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 412 ⟶ 456:
func main() {
ccNumbers(min, max)
}</langsyntaxhighlight>
 
{{out}}
Line 448 ⟶ 492:
Factors: [19250317175041 38500634350081 57750951525121 115501903050241 231003806100481 462007612200961 924015224401921 1848030448803841 3696060897607681 7392121795215361]
</pre>
=={{header|J}}==
 
Brute force:
 
<syntaxhighlight lang="j">a=: {{)v
if.3=y do.1729 return.end.
m=. z=. 2^y-4
f=. 6 12,9*2^}.i.y-1
while.do.
uf=.1+f*m
if.*/1 p: uf do. */x:uf return.end.
m=.m+z
end.
}}</syntaxhighlight>
 
Task examples:
 
<syntaxhighlight lang="j"> a 3
1729
a 4
63973
a 5
26641259752490421121
a 6
1457836374916028334162241
a 7
24541683183872873851606952966798288052977151461406721
a 8
53487697914261966820654105730041031613370337776541835775672321
a 9
58571442634534443082821160508299574798027946748324125518533225605795841</syntaxhighlight>
=={{header|Java}}==
<langsyntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
Line 645 ⟶ 719:
 
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 656 ⟶ 730:
U(9, 950560) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121 = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
function trial_pretest(k::UInt64)
Line 765 ⟶ 838:
end
 
cc_numbers(3, 10)</langsyntaxhighlight>
 
{{out}}
Line 780 ⟶ 853:
 
(takes ~6.5 minutes)
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[PrimeFactorCounts, U]
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}]
Line 807 ⟶ 879:
FindFirstChernickCarmichaelNumber[7]
FindFirstChernickCarmichaelNumber[8]
FindFirstChernickCarmichaelNumber[9]</langsyntaxhighlight>
{{out}}
<pre>{1,1729}
Line 816 ⟶ 888:
{950560,53487697914261966820654105730041031613370337776541835775672321}
{950560,58571442634534443082821160508299574798027946748324125518533225605795841}</pre>
 
=={{header|Nim}}==
{{libheader|bignum}}
Line 826 ⟶ 897:
With these optimizations, the program executes in 4-5 minutes.
 
<langsyntaxhighlight Nimlang="nim">import strutils, sequtils
import bignum
 
Line 901 ⟶ 972:
s.addSep(" × ")
s.add($factor)
stdout.write s, '\n'</langsyntaxhighlight>
 
{{out}}
Line 912 ⟶ 983:
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}}==
<langsyntaxhighlight lang="parigp">
cherCar(n)={
my(C=vector(n));C[1]=6; C[2]=12; for(g=3,n,C[g]=2^(g-2)*9);
Line 922 ⟶ 992:
printf("cherCar(%d): m = %d\n",n,m)}
for(x=3,9,cherCar(x))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 934 ⟶ 1,004:
cherCar(10): m = 3208386195840
</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use 5.020;
use warnings;
use ntheory qw/:all/;
Line 960 ⟶ 1,029:
foreach my $n (3..9) {
chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) });
}</langsyntaxhighlight>
 
{{out}}
Line 972 ⟶ 1,041:
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
 
=={{header|Phix}}==
{{libheader|Phix/mpfr}}
{{trans|Sidef}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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>
Line 1,015 ⟶ 1,083:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre style="font-size: 10px">
Line 1,031 ⟶ 1,099:
{{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...
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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>
Line 1,083 ⟶ 1,151:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,096 ⟶ 1,164:
"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.)
<syntaxhighlight lang="prolog">
<lang Prolog>
?- use_module(library(primality)).
 
Line 1,129 ⟶ 1,196:
 
?- main.
</syntaxhighlight>
</lang>
isprime predicate:
<syntaxhighlight lang="prolog">
<lang Prolog>
prime(N) :-
integer(N),
Line 1,177 ⟶ 1,244:
succ(S0, S1), D1 is D0 >> 1,
factor_2s(S1, D1, S, D).
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 1,189 ⟶ 1,256:
</pre>
=={{header|Python}}==
<langsyntaxhighlight lang="python">
"""
 
Line 1,256 ⟶ 1,323:
k += 1
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,268 ⟶ 1,335:
a(9) has m = 950560
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.03}}
{{trans|Perl}}
Use the ntheory library from Perl 5 for primality testing since it is much, ''much'' faster than Rakus built-in .is-prime method.
 
Use the ntheory library from Perl for primality testing since it is much, ''much'' faster than Raku's built-in .is-prime method.
<lang perl6>use Inline::Perl5;
{{trans|Perl}}
{{libheader|ntheory}}
<syntaxhighlight lang="raku" line>use Inline::Perl5;
use ntheory:from<Perl5> <:all>;
 
sub chernick-factors ($n, $m) {
6*6×$m + 1, 12*12×$m + 1, |((1 .. $n-2).map: { (1 +< $_) *× 9*9×$m + 1 } )
}
 
Line 1,285 ⟶ 1,351:
 
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($_) }
}
 
Line 1,296 ⟶ 1,362:
my $m = chernick-carmichael-number($n);
my @f = chernick-factors($n, $m);
say "U($n, $m): {[*×] @f} = {@f.join(' ⨉ ')}";
}</langsyntaxhighlight>
{{out}}
<pre>U(3, 1): 1729 = 7 ⨉ 13 ⨉ 19
Line 1,306 ⟶ 1,372:
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}}==
<langsyntaxhighlight lang="ruby">func chernick_carmichael_factors (n, m) {
[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...]
}
Line 1,326 ⟶ 1,391:
for n in (3..9) {
chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" })
}</langsyntaxhighlight>
 
{{out}}
Line 1,338 ⟶ 1,403:
a(9) = 5703361 * 11406721 * 17110081 * 34220161 * 68440321 * 136880641 * 273761281 * 547522561 * 1095045121
</pre>
 
=={{header|Wren}}==
{{trans|Go}}
Line 1,344 ⟶ 1,408:
{{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.
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt, BigInts
import "./fmt" for Fmt
 
var min = 3
Line 1,405 ⟶ 1,469:
 
init.call()
ccNumbers.call(min, max)</langsyntaxhighlight>
 
{{out}}
Line 1,443 ⟶ 1,507:
Using GMP (probabilistic primes),
because it is easy and fast to check primeness.
<langsyntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP
 
fcn ccFactors(n,m){ // not re-entrant
Line 1,470 ⟶ 1,534:
}
}
}</langsyntaxhighlight>
<syntaxhighlight lang ="zkl">ccNumbers(3,9);</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/290936...353826"