Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: made some cometic changes, removed calculation with even prime (Carmicahael numbers can't be even). -- ~~~~) |
(→{{header|REXX}}: added a version that shows the Carmichael numbers in sorted order. -- ~~~~) |
||
Line 281: | Line 281: | ||
<br><br>Note that REXX's version of '''modulus''' ('''//''') is really a ''remainder'' function, so a version of |
<br><br>Note that REXX's version of '''modulus''' ('''//''') is really a ''remainder'' function, so a version of |
||
<br>the '''modulus''' function was hard-coded below (when using a negative value). |
<br>the '''modulus''' function was hard-coded below (when using a negative value). |
||
===numbers in order of calculation=== |
|||
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */ |
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */ |
||
numeric digits 30 /*in case user wants bigger nums.*/ |
numeric digits 30 /*in case user wants bigger nums.*/ |
||
Line 397: | Line 398: | ||
──────── a Carmichael number: 61 ∙ 271 ∙ 571 |
──────── a Carmichael number: 61 ∙ 271 ∙ 571 |
||
──────── a Carmichael number: 61 ∙ 241 ∙ 421 |
──────── a Carmichael number: 61 ∙ 241 ∙ 421 |
||
──────── a Carmichael number: 61 ∙ 3361 ∙ 4021 |
|||
69 Carmichael numbers found. |
|||
</pre> |
|||
===numbers in sorted order=== |
|||
With a few lines of code (and using sparse arrays), the Carmichael numbers can be shown in order. |
|||
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes (up to N).*/ |
|||
numeric digits 30 /*in case user wants bigger nums.*/ |
|||
parse arg N .; if N=='' then N=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. */ |
|||
/*Carmichael numbers aren't even.*/ |
|||
do p=3 to N by 2; if \isPrime(p) then iterate /*Not prime? Skip.*/ |
|||
pm=p-1; nps=-p*p; @.=0; min=1e9; max=0 /*some handy-dandy variables.*/ |
|||
do h3=2 to pm; g=h3+p /*find Carmichael #s for this 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 |
|||
carms=carms+1 /*bump the Carmichael # counter. */ |
|||
min=min(min,q); max=max(max,q); @.q=r /*build a list.*/ |
|||
end /*d*/ |
|||
end /*h3*/ |
|||
/*display a list of some Carm #s.*/ |
|||
do j=min to max; if @.j==0 then iterate /*one of the #s ?*/ |
|||
say '──────── a Carmichael number: ' p times j times @.j |
|||
end /*j*/ |
|||
say /*show bueatification blank line.*/ |
|||
end /*p*/ |
|||
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 |
|||
<pre style="height:30ex;overflow:scroll"> |
|||
──────── a Carmichael number: 3 ∙ 11 ∙ 17 |
|||
──────── a Carmichael number: 5 ∙ 13 ∙ 17 |
|||
──────── a Carmichael number: 5 ∙ 17 ∙ 29 |
|||
──────── a Carmichael number: 5 ∙ 29 ∙ 73 |
|||
──────── a Carmichael number: 7 ∙ 13 ∙ 19 |
|||
──────── a Carmichael number: 7 ∙ 19 ∙ 67 |
|||
──────── a Carmichael number: 7 ∙ 23 ∙ 41 |
|||
──────── a Carmichael number: 7 ∙ 31 ∙ 73 |
|||
──────── a Carmichael number: 7 ∙ 73 ∙ 103 |
|||
──────── a Carmichael number: 13 ∙ 37 ∙ 61 |
|||
──────── a Carmichael number: 13 ∙ 61 ∙ 397 |
|||
──────── a Carmichael number: 13 ∙ 97 ∙ 421 |
|||
──────── 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 ∙ 61 ∙ 211 |
|||
──────── a Carmichael number: 31 ∙ 151 ∙ 1171 |
|||
──────── a Carmichael number: 31 ∙ 181 ∙ 331 |
|||
──────── a Carmichael number: 31 ∙ 271 ∙ 601 |
|||
──────── a Carmichael number: 31 ∙ 991 ∙ 15361 |
|||
──────── a Carmichael number: 37 ∙ 73 ∙ 109 |
|||
──────── a Carmichael number: 37 ∙ 109 ∙ 2017 |
|||
──────── a Carmichael number: 37 ∙ 613 ∙ 1621 |
|||
──────── a Carmichael number: 41 ∙ 61 ∙ 101 |
|||
──────── a Carmichael number: 41 ∙ 73 ∙ 137 |
|||
──────── a Carmichael number: 41 ∙ 101 ∙ 461 |
|||
──────── a Carmichael number: 41 ∙ 241 ∙ 521 |
|||
──────── a Carmichael number: 41 ∙ 881 ∙ 12041 |
|||
──────── a Carmichael number: 41 ∙ 1721 ∙ 35281 |
|||
──────── a Carmichael number: 43 ∙ 127 ∙ 211 |
|||
──────── a Carmichael number: 43 ∙ 211 ∙ 337 |
|||
──────── a Carmichael number: 43 ∙ 271 ∙ 5827 |
|||
──────── a Carmichael number: 43 ∙ 433 ∙ 643 |
|||
──────── a Carmichael number: 43 ∙ 547 ∙ 673 |
|||
──────── a Carmichael number: 43 ∙ 631 ∙ 1597 |
|||
──────── a Carmichael number: 43 ∙ 3361 ∙ 3907 |
|||
──────── a Carmichael number: 47 ∙ 1151 ∙ 1933 |
|||
──────── a Carmichael number: 47 ∙ 3359 ∙ 6073 |
|||
──────── a Carmichael number: 47 ∙ 3727 ∙ 5153 |
|||
──────── a Carmichael number: 53 ∙ 79 ∙ 599 |
|||
──────── a Carmichael number: 53 ∙ 157 ∙ 521 |
|||
──────── a Carmichael number: 59 ∙ 1451 ∙ 2089 |
|||
──────── a Carmichael number: 61 ∙ 181 ∙ 1381 |
|||
──────── a Carmichael number: 61 ∙ 241 ∙ 421 |
|||
──────── a Carmichael number: 61 ∙ 271 ∙ 571 |
|||
──────── a Carmichael number: 61 ∙ 277 ∙ 2113 |
|||
──────── a Carmichael number: 61 ∙ 421 ∙ 12841 |
|||
──────── a Carmichael number: 61 ∙ 541 ∙ 3001 |
|||
──────── a Carmichael number: 61 ∙ 661 ∙ 2521 |
|||
──────── a Carmichael number: 61 ∙ 1301 ∙ 19841 |
|||
──────── a Carmichael number: 61 ∙ 3361 ∙ 4021 |
──────── a Carmichael number: 61 ∙ 3361 ∙ 4021 |
||