Rosetta Code

Carmichael 3 strong pseudoprimes: Difference between revisions

Page Discussion

Carmichael 3 strong pseudoprimes (view source)

Revision as of 07:04, 27 September 2014

7,036 bytes removed ,  9 years ago
→‎{{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).
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:
<br>so a version of the &nbsp; '''modulus''' &nbsp; function was hard-coded below.
<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 sortednumerical 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 17=='f1f7'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; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1
!.=0 /*a method of prime memoization. */
/*Carmichael[↓] numbers aren'tprime even# memoization array.*/
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.*/
/*[↑] Carmichael #s aren't even.*/
 
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */
gpm=g*pm; do dnpsh3=1((nps//h3)+h3)//h3 to g-1 /*shortcut stuff. */
ifdo g*pm//d\==01 for then iterateg-1
if ((npsgpm//h3)+h3)//h3d\==d//h30 then iterate
qif npsh3\==1+pm*g%d;//h3 if \isPrime(q) then iterate
q=1+gpm%d; if \isPrime(q) then iterate
r=1+p*q%h3; if q*r//pm\==1 then iterate
if \isPrime(r) then iterate
Line 945 ⟶ 815:
end /*d*/
end /*h3*/
$=0 /*display a list of some Carm #s.*/
do j=min to max by 2; if @.j==0 then iterate; /*one of the #s?*/ $=1
say '──────── a Carmichael number: ' p times j times @.j
end /*j*/
say if $ then say /*show bueatification blank line.*/
end /*p*/
 
Line 955 ⟶ 825:
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<23 3then 5return 70; 11if 13')\x//2==0 then return do0; if !.x// 3=1;=0 then return 1; end0
if right(x<17,1)==5 then return 0; if x//2==0 then return 0; if x//3 7==0 then return 0
if right(x,1)//11==50 then return 0; if x//713==0 then return 0
if x//17==0 then return 0; do i=11 by 6 until i*i>x; if x// i 19==0 then return 0
do i=23 by 6 until i*i>x; if x//( i+2) ==0 then return 0
end if x/*i*/(i+2)==0 then return 0
end /*i*/
!.x=1; return 1</lang>
'''output''' when using the default input:
<pre style="height:50ex">
──────── a Carmichael number: 3 ∙ 11 ∙ 17
Line 976 ⟶ 847:
──────── a Carmichael number: 7 ∙ 31 ∙ 73
──────── a Carmichael number: 7 ∙ 73 ∙ 103
 
 
──────── a Carmichael number: 13 ∙ 37 ∙ 61
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/222706"