Chernick's Carmichael numbers: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: note use of 'ntheory' module) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 56: | Line 56: | ||
=={{header|C}}== |
=={{header|C}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang=c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <gmp.h> |
#include <gmp.h> |
||
Line 106: | Line 106: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 121: | Line 121: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang=cpp>#include <gmp.h> |
||
#include <iostream> |
#include <iostream> |
||
Line 206: | Line 206: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 222: | Line 222: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang=fsharp> |
||
// Generate Chernick's Carmichael numbers. Nigel Galloway: June 1st., 2019 |
// 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 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 228: | Line 228: | ||
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)) |
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 |
[4..9] |> Seq.iter cherCar |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 242: | Line 242: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
===Basic only=== |
===Basic only=== |
||
< |
<syntaxhighlight lang=freebasic>#include "isprime.bas" |
||
Function PrimalityPretest(k As Integer) As Boolean |
Function PrimalityPretest(k As Integer) As Boolean |
||
Line 286: | Line 286: | ||
Loop |
Loop |
||
Next n |
Next n |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Basic only=== |
===Basic only=== |
||
< |
<syntaxhighlight lang=go>package main |
||
import ( |
import ( |
||
Line 347: | Line 347: | ||
func main() { |
func main() { |
||
ccNumbers(3, 9) |
ccNumbers(3, 9) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 369: | Line 369: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=go>package main |
||
import ( |
import ( |
||
Line 463: | Line 463: | ||
func main() { |
func main() { |
||
ccNumbers(min, max) |
ccNumbers(min, max) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 504: | Line 504: | ||
Brute force: |
Brute force: |
||
< |
<syntaxhighlight lang=J>a=: {{)v |
||
if.3=y do.1729 return.end. |
if.3=y do.1729 return.end. |
||
m=. z=. 2^y-4 |
m=. z=. 2^y-4 |
||
Line 513: | Line 513: | ||
m=.m+z |
m=.m+z |
||
end. |
end. |
||
}}</ |
}}</syntaxhighlight> |
||
Task examples: |
Task examples: |
||
< |
<syntaxhighlight lang=J> a 3 |
||
1729 |
1729 |
||
a 4 |
a 4 |
||
Line 530: | Line 530: | ||
53487697914261966820654105730041031613370337776541835775672321 |
53487697914261966820654105730041031613370337776541835775672321 |
||
a 9 |
a 9 |
||
58571442634534443082821160508299574798027946748324125518533225605795841</ |
58571442634534443082821160508299574798027946748324125518533225605795841</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang=java> |
||
import java.math.BigInteger; |
import java.math.BigInteger; |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
Line 728: | Line 728: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 741: | Line 741: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang=julia>using Primes |
||
function trial_pretest(k::UInt64) |
function trial_pretest(k::UInt64) |
||
Line 848: | Line 848: | ||
end |
end |
||
cc_numbers(3, 10)</ |
cc_numbers(3, 10)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 865: | Line 865: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang=Mathematica>ClearAll[PrimeFactorCounts, U] |
||
PrimeFactorCounts[n_Integer] := Total[FactorInteger[n][[All, 2]]] |
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}] |
U[n_, m_] := (6 m + 1) (12 m + 1) Product[2^i 9 m + 1, {i, 1, n - 2}] |
||
Line 890: | Line 890: | ||
FindFirstChernickCarmichaelNumber[7] |
FindFirstChernickCarmichaelNumber[7] |
||
FindFirstChernickCarmichaelNumber[8] |
FindFirstChernickCarmichaelNumber[8] |
||
FindFirstChernickCarmichaelNumber[9]</ |
FindFirstChernickCarmichaelNumber[9]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1,1729} |
<pre>{1,1729} |
||
Line 909: | Line 909: | ||
With these optimizations, the program executes in 4-5 minutes. |
With these optimizations, the program executes in 4-5 minutes. |
||
< |
<syntaxhighlight lang=Nim>import strutils, sequtils |
||
import bignum |
import bignum |
||
Line 984: | Line 984: | ||
s.addSep(" × ") |
s.addSep(" × ") |
||
s.add($factor) |
s.add($factor) |
||
stdout.write s, '\n'</ |
stdout.write s, '\n'</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 997: | Line 997: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang=parigp> |
||
cherCar(n)={ |
cherCar(n)={ |
||
my(C=vector(n));C[1]=6; C[2]=12; for(g=3,n,C[g]=2^(g-2)*9); |
my(C=vector(n));C[1]=6; C[2]=12; for(g=3,n,C[g]=2^(g-2)*9); |
||
Line 1,005: | Line 1,005: | ||
printf("cherCar(%d): m = %d\n",n,m)} |
printf("cherCar(%d): m = %d\n",n,m)} |
||
for(x=3,9,cherCar(x)) |
for(x=3,9,cherCar(x)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,020: | Line 1,020: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang=perl>use 5.020; |
||
use warnings; |
use warnings; |
||
use ntheory qw/:all/; |
use ntheory qw/:all/; |
||
Line 1,043: | Line 1,043: | ||
foreach my $n (3..9) { |
foreach my $n (3..9) { |
||
chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) }); |
chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) }); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,059: | Line 1,059: | ||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
{{trans|Sidef}} |
{{trans|Sidef}} |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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: #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,098: | Line 1,098: | ||
<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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre style="font-size: 10px"> |
<pre style="font-size: 10px"> |
||
Line 1,114: | Line 1,114: | ||
{{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> |
{{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... |
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... |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 1,166: | Line 1,166: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,182: | Line 1,182: | ||
=={{header|Prolog}}== |
=={{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.) |
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> |
||
?- use_module(library(primality)). |
?- use_module(library(primality)). |
||
Line 1,212: | Line 1,212: | ||
?- main. |
?- main. |
||
</syntaxhighlight> |
|||
</lang> |
|||
isprime predicate: |
isprime predicate: |
||
< |
<syntaxhighlight lang=Prolog> |
||
prime(N) :- |
prime(N) :- |
||
integer(N), |
integer(N), |
||
Line 1,260: | Line 1,260: | ||
succ(S0, S1), D1 is D0 >> 1, |
succ(S0, S1), D1 is D0 >> 1, |
||
factor_2s(S1, D1, S, D). |
factor_2s(S1, D1, S, D). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,272: | Line 1,272: | ||
</pre> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang=python> |
||
""" |
""" |
||
Line 1,339: | Line 1,339: | ||
k += 1 |
k += 1 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,358: | Line 1,358: | ||
{{trans|Perl}} |
{{trans|Perl}} |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
<lang |
<syntaxhighlight lang=raku line>use Inline::Perl5; |
||
use ntheory:from<Perl5> <:all>; |
use ntheory:from<Perl5> <:all>; |
||
Line 1,380: | Line 1,380: | ||
my @f = chernick-factors($n, $m); |
my @f = chernick-factors($n, $m); |
||
say "U($n, $m): {[×] @f} = {@f.join(' ⨉ ')}"; |
say "U($n, $m): {[×] @f} = {@f.join(' ⨉ ')}"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>U(3, 1): 1729 = 7 ⨉ 13 ⨉ 19 |
<pre>U(3, 1): 1729 = 7 ⨉ 13 ⨉ 19 |
||
Line 1,391: | Line 1,391: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang=ruby>func chernick_carmichael_factors (n, m) { |
||
[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...] |
[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...] |
||
} |
} |
||
Line 1,409: | Line 1,409: | ||
for n in (3..9) { |
for n in (3..9) { |
||
chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" }) |
chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" }) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,427: | Line 1,427: | ||
{{libheader|Wren-fmt}} |
{{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. |
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. |
||
< |
<syntaxhighlight lang=ecmascript>import "/big" for BigInt, BigInts |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 1,488: | Line 1,488: | ||
init.call() |
init.call() |
||
ccNumbers.call(min, max)</ |
ccNumbers.call(min, max)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,526: | Line 1,526: | ||
Using GMP (probabilistic primes), |
Using GMP (probabilistic primes), |
||
because it is easy and fast to check primeness. |
because it is easy and fast to check primeness. |
||
< |
<syntaxhighlight lang=zkl>var [const] BI=Import("zklBigNum"); // libGMP |
||
fcn ccFactors(n,m){ // not re-entrant |
fcn ccFactors(n,m){ // not re-entrant |
||
Line 1,553: | Line 1,553: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<lang |
<syntaxhighlight lang=zkl>ccNumbers(3,9);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |