Carmichael 3 strong pseudoprimes: Difference between revisions

 

 

 

 

 

=={{header|Ada}}==

 

Uses the Miller_Rabin package from

[[Miller-Rabin primality test#ordinary integers]].

 

procedure Nemesis is

end if;

end loop;

 

{{out}}

61 * 241 * 421 = 6189121

61 * 3361 * 4021 = 824389441</pre>

 

=={{header|C}}==

#include <stdio.h>

 

return 0;

}

{{out}}

<pre>

61 3361 4021

</pre>

 

=={{header|D}}==

 

bool isPrime(in uint n) pure nothrow @nogc {

}

}

{{out}}

<pre>3 x 11 x 17

61 x 241 x 421

61 x 3361 x 4021</pre>

 

=={{header|EchoLisp}}==

;; charmichaël numbers up to N-th prime ; 61 is 18-th prime

(define (charms (N 18) local: (h31 0) (Prime2 0) (Prime3 0))

#:when (= 1 (modulo (* Prime2 Prime3) (1- Prime1)))

(printf " 💥 %12d = %d x %d x %d" (* Prime1 Prime2 Prime3) Prime1 Prime2 Prime3)))

{{out}}

(charms 3)

💥 561 = 3 x 11 x 17

💥 6189121 = 61 x 241 x 421

💥 824389441 = 61 x 3361 x 4021

 

=={{header|Haskell}}==

{{trans|Ruby}}

{{Works with|GHC|7.4.1}}

{{Works with|primes|0.2.1.0}}

 

import Data.Numbers.Primes

return (p, q, r)

 

{{out}}

<pre>

(61,3361,4021)

</pre>

=={{header|Icon}} and {{header|Unicon}}==

 

The following works in both languages.

 

procedure main(A)

procedure format(p1,p2,p3)

return left(p1||" * "||p2||" * "||p3,20)||" = "||(p1*p2*p3)

 

Output, with middle lines elided:

->

</pre>

 

=={{header|Julia}}==

This solution is a straightforward implementation of the algorithm of the Jameson paper cited in the task description. Just for fun, I use Julia's capacity to accommodate Unicode identifiers to match some of the paper's symbols to the variables used in the <tt>carmichael</tt> function.

 

'''Function'''

for p in primes(pmax)

for h₃ in 2:(p-1)

for Δ in 1:(h₃+p-1)

append!(car, [p, q, r])

end

end

end

 

'''Main'''

car = carmichael(hi)

 

for j in sortperm(1:size(car)[2], by=x->(car[1,x], car[2,x], car[3,x]))

if p != curp

curp = p

tcnt = 0

end

tcnt += 1

end

end

 

{{out}}

 

 

 

p = 17

 

p = 19

 

p = 23

 

p = 29

 

p = 31

 

p = 41

 

p = 43

 

p = 47

 

p = 53

 

p = 59

 

p = 61

 

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Cases[Table[{p1, h3, d}, {p1, Array[Prime, PrimePi@61]}, {h3, 2,

p1 - 1}, {d, 1, h3 + p1 - 1}], {p1_Integer, h3_, d_} /;

Infinity], {p1_, p2_, h3_} /; PrimeQ[1 + Floor[p1 p2/h3]] :> {p1,

p2, 1 + Floor[p1 p2/h3]}], {p1_, p2_, p3_} /;

 

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

my(v=List(),q,r);

for(h=2,p-1,

Set(v)

};

{{out}}

<pre>561, 1105, 2465, 10585, 1729, 2821, 6601, 8911, 15841, 52633, 29341, 46657, 115921, 314821, 530881, 162401, 7207201, 334153, 1024651, 1615681, 3581761, 5444489, 399001, 512461, 1193221, 1857241, 5049001, 5481451, 471905281, 294409, 488881, 1461241, 8134561, 36765901, 252601, 410041, 1909001, 5148001, 7519441, 434932961, 2489462641, 1152271, 3057601, 5968873, 6868261, 11972017, 14913991, 15829633, 43331401, 67902031, 368113411, 564651361, 104569501, 902645857, 958762729, 2508013, 4335241, 17316001, 178837201, 6189121, 9439201, 15247621, 35703361, 60957361, 99036001, 101649241, 329769721, 824389441, 1574601601, 10267951, 163954561, 7991602081,</pre>

=={{header|Perl}}==

{{libheader|ntheory}}

 

forprimes { my $p = $_;

}

}

{{out}}

<pre>

61 x 3361 x 4021 = 824389441

</pre>

{{out}}

=={{header|PicoLisp}}==

(% (+ Y (% X Y)) Y) )

(prinl)

=={{header|PL/I}}==

declare (Prime1, Prime2, Prime3, h3, d) fixed binary (31);

 

/* Uses is_prime from Rosetta Code PL/I. */

 

Results:

<pre>

61 x 3361 x 4021

</pre>

 

=={{header|Python}}==

'''

Extensible sieve of Eratosthenes

ans = sorted(sum((carmichael(n) for n in range(62) if isprime(n)), []))

{{out}}

<pre>(3, 11, 17), (5, 13, 17), (5, 17, 29), (5, 29, 73), (7, 13, 19),

(61, 181, 5521), (61, 241, 421), (61, 271, 571), (61, 277, 2113), (61, 421, 12841),

(61, 541, 3001), (61, 661, 2521), (61, 1301, 19841), (61, 3361, 4021)</pre>

=={{header|Racket}}==

#lang racket

(require math)

(displayln (list p1 p2 p3 '=> (* p1 p2 p3))))))

(next (+ d 1))))))

Output:

(3 11 17 => 561)

(5 29 73 => 10585)

(61 241 421 => 6189121)

(61 3361 4021 => 824389441)

=={{header|REXX}}==

 

/*[↑] prime number memoization array. */

 

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

'''output''' &nbsp; when using the default input:

 

 

 

 

</pre>

<pre>

</pre>

 

=={{header|Ruby}}==

{{works with|Ruby|1.9}}

 

require 'prime'

end

puts

 

{{out}}

 

=={{header|Rust}}==

fn is_prime(n: i64) -> bool {

if n > 1 {

.count(); // Evaluate entire iterator

}

{{out}}

<pre>

(61, 3361, 4021)

</pre>

=={{header|Seed7}}==

The function [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime] below is borrowed from the [http://seed7.sourceforge.net/algorith Seed7 algorithm collection].

 

const func boolean: isPrime (in integer: number) is func

end if;

end for;

 

{{out}}

61 * 3361 * 4021 = 824389441

</pre>

=={{header|Sidef}}==

{{trans|Perl}}

 

}

}

 

{{out}}

61 x 3361 x 4021 = 824389441

</pre>

 

=={{header|Tcl}}==

Using the primality tester from [[Miller-Rabin primality test#Tcl|the Miller-Rabin task]]...

set carmichaels {}

for {set p1 2} {$p1 <= $limit} {incr p1} {

}

return $carmichaels

Demonstrating:

puts "[expr {[llength $results]/4}] Carmichael numbers found"

foreach {p1 p2 p3 c} $results {

puts "$p1 x $p2 x $p3 = $c"

{{out}}

<pre>

61 x 241 x 421 = 6189121

61 x 3361 x 4021 = 824389441

</pre>

 

=={{header|zkl}}==

Using the Miller-Rabin primality test in lib GMP.

primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61);

var p2,p3;

{ T(p1,p2,p3) } // return list of three primes in Carmichael number

]];

cs.pump(Console.println,fcn([(p1,p2,p3)]){

{{out}}

<pre>