Chernick's Carmichael numbers: Difference between revisions
m
syntax highlighting fixup automation
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: note use of 'ntheory' module) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 56:
=={{header|C}}==
{{libheader|GMP}}
<
#include <stdlib.h>
#include <gmp.h>
Line 106:
return 0;
}</
{{out}}
<pre>
Line 121:
=={{header|C++}}==
{{libheader|GMP}}
<
#include <iostream>
Line 206:
return 0;
}</
{{out}}
<pre>
Line 222:
=={{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))
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))
[4..9] |> Seq.iter cherCar
</syntaxhighlight>
{{out}}
<pre>
Line 242:
=={{header|FreeBASIC}}==
===Basic only===
<
Function PrimalityPretest(k As Integer) As Boolean
Line 286:
Loop
Next n
Sleep</
=={{header|Go}}==
===Basic only===
<
import (
Line 347:
func main() {
ccNumbers(3, 9)
}</
{{out}}
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.
<
import (
Line 463:
func main() {
ccNumbers(min, max)
}</
{{out}}
Line 504:
Brute force:
<
if.3=y do.1729 return.end.
m=. z=. 2^y-4
Line 513:
m=.m+z
end.
}}</
Task examples:
<
1729
a 4
Line 530:
53487697914261966820654105730041031613370337776541835775672321
a 9
58571442634534443082821160508299574798027946748324125518533225605795841</
=={{header|Java}}==
<
import java.math.BigInteger;
import java.util.ArrayList;
Line 728:
}
</syntaxhighlight>
{{out}}
<pre>
Line 741:
=={{header|Julia}}==
<
function trial_pretest(k::UInt64)
Line 848:
end
cc_numbers(3, 10)</
{{out}}
Line 865:
=={{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}]
Line 890:
FindFirstChernickCarmichaelNumber[7]
FindFirstChernickCarmichaelNumber[8]
FindFirstChernickCarmichaelNumber[9]</
{{out}}
<pre>{1,1729}
Line 909:
With these optimizations, the program executes in 4-5 minutes.
<
import bignum
Line 984:
s.addSep(" × ")
s.add($factor)
stdout.write s, '\n'</
{{out}}
Line 997:
=={{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);
Line 1,005:
printf("cherCar(%d): m = %d\n",n,m)}
for(x=3,9,cherCar(x))
</syntaxhighlight>
{{out}}
<pre>
Line 1,020:
=={{header|Perl}}==
{{libheader|ntheory}}
<
use warnings;
use ntheory qw/:all/;
Line 1,043:
foreach my $n (3..9) {
chernick_carmichael_number($n, sub (@f) { say "a($n) = ", vecprod(@f) });
}</
{{out}}
Line 1,059:
{{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>
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: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre style="font-size: 10px">
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>
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>
Line 1,166:
<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>
Line 1,182:
=={{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)).
Line 1,212:
?- main.
</syntaxhighlight>
isprime predicate:
<
prime(N) :-
integer(N),
Line 1,260:
succ(S0, S1), D1 is D0 >> 1,
factor_2s(S1, D1, S, D).
</syntaxhighlight>
{{Out}}
<pre>
Line 1,272:
</pre>
=={{header|Python}}==
<
"""
Line 1,339:
k += 1
</syntaxhighlight>
{{out}}
Line 1,358:
{{trans|Perl}}
{{libheader|ntheory}}
<syntaxhighlight lang=raku
use ntheory:from<Perl5> <:all>;
Line 1,380:
my @f = chernick-factors($n, $m);
say "U($n, $m): {[×] @f} = {@f.join(' ⨉ ')}";
}</
{{out}}
<pre>U(3, 1): 1729 = 7 ⨉ 13 ⨉ 19
Line 1,391:
=={{header|Sidef}}==
<
[6*m + 1, 12*m + 1, {|i| 2**i * 9*m + 1 }.map(1 .. n-2)...]
}
Line 1,409:
for n in (3..9) {
chernick_carmichael_number(n, {|*f| say "a(#{n}) = #{f.join(' * ')}" })
}</
{{out}}
Line 1,427:
{{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.
<
import "/fmt" for Fmt
Line 1,488:
init.call()
ccNumbers.call(min, max)</
{{out}}
Line 1,526:
Using GMP (probabilistic primes),
because it is easy and fast to check primeness.
<
fcn ccFactors(n,m){ // not re-entrant
Line 1,553:
}
}
}</
<syntaxhighlight lang
{{out}}
<pre>
|