Carmichael 3 strong pseudoprimes

Carmichael 3 strong pseudoprimes
You are encouraged to solve this task according to the task description, using any language you may know.

A lot of composite numbers can be detected by the Miller Rabin Test, but there are some that evade it.

The purpose of this task is to investigate such numbers. The method suggested is based on Notes by G.J.O Jameson March 2010

The objective is to find Carmichael numbers of the form Prime1 X Prime2 X Prime3.

Prime1 < Prime2 < Prime3 for all Prime1 upto 61 see page 7 of Notes by G.J.O Jameson March 2010.

For a given Prime1

for 1 < h3 < Prime1

g=h3+Prime1

for 0 < d < h3+Prime1

if (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3

then

Prime2 = 1 + ((Prime1-1) * g/d)

next d if Prime2 is not prime

Prime3 = 1 + (Prime1*Prime2/h3)

next d if Prime3 is not prime

next d if (Prime2*Prime3) mod (Prime1-1) not equal 1

Prime1 * Prime2 * Prime3 is a Carmichael Number

Related Tasks:

Miller-Rabin primality test

REXX

The REXX if statements could be optimized within the do h3 loop by unrolling them, and
also by implementing a faster isPrime function.

Note that REXX's version of modulus (//) is really a remainder function, so a version of
the modulus function was hard-coded below (when using a negative value). <lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */ numeric digits 30 /*in case user wants bigger nums.*/ parse arg h .; if h== then h=61 /*allow user to specify the limit*/ if 1=='f1'x then times='af'x /*if EBCDIC machine, use a bullet*/

            else times='f9'x          /* " ASCII     "      "  "   "   */

carms=0 /*number of Carmichael #s so far.*/ !.=0 /*a method of prime memoization. */

     do j=1  to h  by 2;  p=j;  if p==1 then p=2
     if \isPrime(p) then iterate      /*Not prime?  Then keep truckin'.*/
     pm=p-1                           /*use this for "prime less one." */
     nps=-p*p                         /*another handy-dandy variable.  */

       do h3=2  to  pm;   g=h3+p
          do d=1  to g-1
          if g*pm//d\==0 | ((nps//h3)+h3)//h3\==d//h3  then iterate
          q=1+pm*g%d;    if \isPrime(q) | q==p         then iterate
          r=1+p*q%h3;    if \isPrime(r) | q*r//pm\==1  then iterate
          say '──────── a Carmichael number: '  p  times  q  times  r
          carms=carms+1               /*bump the Carmichael # counter. */
          end   /*d*/
       end      /*h3*/
     say                              /*show bueatification blank line.*/
     end        /*j*/

say; say carms ' Carmichael numbers found.' exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────ISPRIME subroutine──────────────────*/ isPrime: procedure expose !.; parse arg x; if !.x then return 1 if wordpos(x,'2 3 5 7')\==0 then do;  !.x=1; return 1; end if x<11 then return 0; if x//2==0 then return 0; if x//3==0 then return 0

                do i=5  by 6  until i*i>x;  if x//i==0      then return 0
                                            if x//(i+2)==0  then return 0
                end  /*i*/

!.x=1 return 1</lang> output when using the default input

──────── a Carmichael number:  3 ∙ 11 ∙ 17

──────── a Carmichael number:  5 ∙ 29 ∙ 73
──────── a Carmichael number:  5 ∙ 17 ∙ 29
──────── a Carmichael number:  5 ∙ 13 ∙ 17

──────── a Carmichael number:  7 ∙ 19 ∙ 67
──────── a Carmichael number:  7 ∙ 31 ∙ 73
──────── a Carmichael number:  7 ∙ 13 ∙ 31
──────── a Carmichael number:  7 ∙ 23 ∙ 41
──────── a Carmichael number:  7 ∙ 73 ∙ 103
──────── a Carmichael number:  7 ∙ 13 ∙ 19


──────── a Carmichael number:  13 ∙ 61 ∙ 397
──────── a Carmichael number:  13 ∙ 37 ∙ 241
──────── a Carmichael number:  13 ∙ 97 ∙ 421
──────── a Carmichael number:  13 ∙ 37 ∙ 97
──────── a Carmichael number:  13 ∙ 37 ∙ 61

──────── a Carmichael number:  17 ∙ 41 ∙ 233
──────── a Carmichael number:  17 ∙ 353 ∙ 1201

──────── a Carmichael number:  19 ∙ 43 ∙ 409
──────── a Carmichael number:  19 ∙ 199 ∙ 271

──────── a Carmichael number:  23 ∙ 199 ∙ 353

──────── a Carmichael number:  29 ∙ 113 ∙ 1093
──────── a Carmichael number:  29 ∙ 197 ∙ 953

──────── a Carmichael number:  31 ∙ 991 ∙ 15361
──────── a Carmichael number:  31 ∙ 61 ∙ 631
──────── a Carmichael number:  31 ∙ 151 ∙ 1171
──────── a Carmichael number:  31 ∙ 61 ∙ 271
──────── a Carmichael number:  31 ∙ 61 ∙ 211
──────── a Carmichael number:  31 ∙ 271 ∙ 601
──────── a Carmichael number:  31 ∙ 181 ∙ 331

──────── a Carmichael number:  37 ∙ 109 ∙ 2017
──────── a Carmichael number:  37 ∙ 73 ∙ 541
──────── a Carmichael number:  37 ∙ 613 ∙ 1621
──────── a Carmichael number:  37 ∙ 73 ∙ 181
──────── a Carmichael number:  37 ∙ 73 ∙ 109

──────── a Carmichael number:  41 ∙ 1721 ∙ 35281
──────── a Carmichael number:  41 ∙ 881 ∙ 12041
──────── a Carmichael number:  41 ∙ 101 ∙ 461
──────── a Carmichael number:  41 ∙ 241 ∙ 761
──────── a Carmichael number:  41 ∙ 241 ∙ 521
──────── a Carmichael number:  41 ∙ 73 ∙ 137
──────── a Carmichael number:  41 ∙ 61 ∙ 101

──────── a Carmichael number:  43 ∙ 631 ∙ 13567
──────── a Carmichael number:  43 ∙ 271 ∙ 5827
──────── a Carmichael number:  43 ∙ 127 ∙ 2731
──────── a Carmichael number:  43 ∙ 127 ∙ 1093
──────── a Carmichael number:  43 ∙ 211 ∙ 757
──────── a Carmichael number:  43 ∙ 631 ∙ 1597
──────── a Carmichael number:  43 ∙ 127 ∙ 211
──────── a Carmichael number:  43 ∙ 211 ∙ 337
──────── a Carmichael number:  43 ∙ 433 ∙ 643
──────── a Carmichael number:  43 ∙ 547 ∙ 673
──────── a Carmichael number:  43 ∙ 3361 ∙ 3907

──────── a Carmichael number:  47 ∙ 3359 ∙ 6073
──────── a Carmichael number:  47 ∙ 1151 ∙ 1933
──────── a Carmichael number:  47 ∙ 3727 ∙ 5153

──────── a Carmichael number:  53 ∙ 157 ∙ 2081
──────── a Carmichael number:  53 ∙ 79 ∙ 599
──────── a Carmichael number:  53 ∙ 157 ∙ 521

──────── a Carmichael number:  59 ∙ 1451 ∙ 2089

──────── a Carmichael number:  61 ∙ 421 ∙ 12841
──────── a Carmichael number:  61 ∙ 181 ∙ 5521
──────── a Carmichael number:  61 ∙ 1301 ∙ 19841
──────── a Carmichael number:  61 ∙ 277 ∙ 2113
──────── a Carmichael number:  61 ∙ 181 ∙ 1381
──────── a Carmichael number:  61 ∙ 541 ∙ 3001
──────── a Carmichael number:  61 ∙ 661 ∙ 2521
──────── a Carmichael number:  61 ∙ 271 ∙ 571
──────── a Carmichael number:  61 ∙ 241 ∙ 421
──────── a Carmichael number:  61 ∙ 3361 ∙ 4021


69  Carmichael numbers found.

Ruby

<lang ruby>

1. Generate Charmichael Numbers
3. Nigel_Galloway
4. November 30th., 2012.

require 'prime' Integer.each_prime(61) {|p|

 (2...p).each {|h3|
   g = h3+p
   (1...g).each {|d|
     if (g*(p-1)) % d == 0 and (-1*p*p) % h3 == d % h3 then
       q = 1+((p-1)*g/d)
       next if not q.prime?
       r = 1+(p*q/h3)
       next if not r.prime? or not (q*r) % (p-1) == 1
       puts "#{p} X #{q} X #{r}" 
     end
   }
 }
 puts ""

} </lang>

Output:

3 X 11 X 17

5 X 29 X 73
5 X 17 X 29
5 X 13 X 17

7 X 19 X 67
7 X 31 X 73
7 X 13 X 31
7 X 23 X 41
7 X 73 X 103
7 X 13 X 19


13 X 61 X 397
13 X 37 X 241
13 X 97 X 421
13 X 37 X 97
13 X 37 X 61

17 X 41 X 233
17 X 353 X 1201

19 X 43 X 409
19 X 199 X 271

23 X 199 X 353

29 X 113 X 1093
29 X 197 X 953

31 X 991 X 15361
31 X 61 X 631
31 X 151 X 1171
31 X 61 X 271
31 X 61 X 211
31 X 271 X 601
31 X 181 X 331

37 X 109 X 2017
37 X 73 X 541
37 X 613 X 1621
37 X 73 X 181
37 X 73 X 109

41 X 1721 X 35281
41 X 881 X 12041
41 X 101 X 461
41 X 241 X 761
41 X 241 X 521
41 X 73 X 137
41 X 61 X 101

43 X 631 X 13567
43 X 271 X 5827
43 X 127 X 2731
43 X 127 X 1093
43 X 211 X 757
43 X 631 X 1597
43 X 127 X 211
43 X 211 X 337
43 X 433 X 643
43 X 547 X 673
43 X 3361 X 3907

47 X 3359 X 6073
47 X 1151 X 1933
47 X 3727 X 5153

53 X 157 X 2081
53 X 79 X 599
53 X 157 X 521

59 X 1451 X 2089

61 X 421 X 12841
61 X 181 X 5521
61 X 1301 X 19841
61 X 277 X 2113
61 X 181 X 1381
61 X 541 X 3001
61 X 661 X 2521
61 X 271 X 571
61 X 241 X 421
61 X 3361 X 4021