Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: corrected quote strings for STYLE html tags.) |
(→{{header|REXX}}: changed the inner DO loop to be faster, added shortcut calculations, used a flag to suppress blank lines, increased initial prime memoization list, removed 1st version (unsorted list).) |
||
| Line 790: | Line 790: | ||
<br>so a version of the '''modulus''' function was hard-coded below. |
<br>so a version of the '''modulus''' function was hard-coded below. |
||
<br>(It was necessary to use '''modulus''' instead of '''remainder''' when using a negative value.) |
<br>(It was necessary to use '''modulus''' instead of '''remainder''' when using a negative value.) |
||
===numbers in order of calculation=== |
|||
<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. */ |
|||
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 then iterate |
|||
if ((nps//h3)+h3)//h3\==d//h3 then iterate |
|||
q=1+pm*g%d; if \isPrime(q) then iterate |
|||
r=1+p*q%h3; if q*r//pm\==1 then iterate |
|||
if \isPrime(r) 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 by 2; 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 11 13')\==0 then do; !.x=1; return 1; end |
|||
if x<17 then return 0; if x//2==0 then return 0; if x//3==0 then return 0 |
|||
if right(x,1)==5 then return 0; if x//7==0 then return 0 |
|||
do i=11 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 |
|||
<br><br>The Carmichael numbers were grouped by the first Carmichael number. |
|||
<pre style="height:50ex"> |
|||
──────── 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. |
|||
</pre> |
|||
<br>The Carmichael numbers are shown in numerical 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).*/ |
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes (up to N).*/ |
||
numeric digits 30 /*in case user wants bigger nums.*/ |
numeric digits 30 /*in case user wants bigger nums.*/ |
||
parse arg N .; if N=='' then N=61 |
parse arg N .; if N=='' then N=61 /*allow user to specify the limit*/ |
||
if |
if 7=='f7'x then times='af'x /*if EBCDIC machine, use a bullet*/ |
||
else times='f9'x /* " ASCII " " " " */ |
else times='f9'x /* " ASCII " " " " */ |
||
carms=0 /*number of Carmichael #s so far.*/ |
carms=0 /*number of Carmichael #s so far.*/ |
||
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1 |
|||
!.=0 /*a method of prime memoization. */ |
|||
/* |
/*[↓] prime # memoization array.*/ |
||
do p=3 to N by 2; if \isPrime(p) then iterate /*Not prime? Skip.*/ |
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.*/ |
pm=p-1; nps=-p*p; @.=0; min=1e9; max=0 /*some handy-dandy variables.*/ |
||
/*[↑] Carmichael #s aren't even.*/ |
|||
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */ |
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */ |
||
gpm=g*pm; npsh3=((nps//h3)+h3)//h3 /*shortcut stuff. */ |
|||
do d=1 for g-1 |
|||
if |
if gpm//d\==0 then iterate |
||
if npsh3\==d//h3 then iterate |
|||
q=1+gpm%d; if \isPrime(q) then iterate |
|||
r=1+p*q%h3; if q*r//pm\==1 then iterate |
r=1+p*q%h3; if q*r//pm\==1 then iterate |
||
if \isPrime(r) then iterate |
if \isPrime(r) then iterate |
||
| Line 945: | Line 815: | ||
end /*d*/ |
end /*d*/ |
||
end /*h3*/ |
end /*h3*/ |
||
$=0 /*display a list of some Carm #s.*/ |
|||
do j=min to max by 2; if @.j==0 then iterate |
do j=min to max by 2; if @.j==0 then iterate; $=1 |
||
say '──────── a Carmichael number: ' p times j times @.j |
say '──────── a Carmichael number: ' p times j times @.j |
||
end /*j*/ |
end /*j*/ |
||
if $ then say /*show bueatification blank line.*/ |
|||
end /*p*/ |
end /*p*/ |
||
| Line 955: | Line 825: | ||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────ISPRIME subroutine──────────────────*/ |
/*──────────────────────────────────ISPRIME subroutine──────────────────*/ |
||
isPrime: procedure expose !.; parse arg x; if !.x then return 1 |
isPrime: procedure expose !.; parse arg x; if !.x then return 1 |
||
if |
if x<23 then return 0; if x//2==0 then return 0; if x// 3==0 then return 0 |
||
if x |
if right(x,1)==5 then return 0; if x// 7==0 then return 0 |
||
if |
if x//11==0 then return 0; if x//13==0 then return 0 |
||
if x//17==0 then return 0; if x//19==0 then return 0 |
|||
do i=23 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> |
!.x=1; return 1</lang> |
||
'''output''' when using the default input |
'''output''' when using the default input: |
||
<pre style="height:50ex"> |
<pre style="height:50ex"> |
||
──────── a Carmichael number: 3 ∙ 11 ∙ 17 |
──────── a Carmichael number: 3 ∙ 11 ∙ 17 |
||
| Line 976: | Line 847: | ||
──────── a Carmichael number: 7 ∙ 31 ∙ 73 |
──────── a Carmichael number: 7 ∙ 31 ∙ 73 |
||
──────── a Carmichael number: 7 ∙ 73 ∙ 103 |
──────── a Carmichael number: 7 ∙ 73 ∙ 103 |
||
──────── a Carmichael number: 13 ∙ 37 ∙ 61 |
──────── a Carmichael number: 13 ∙ 37 ∙ 61 |
||