Anonymous user
Carmichael 3 strong pseudoprimes: Difference between revisions
Carmichael 3 strong pseudoprimes (view source)
Revision as of 06:45, 11 December 2012
, 11 years ago→{{header|REXX}}: added a version that shows the Carmichael numbers in sorted order. -- ~~~~
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:
<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).
===numbers in order of calculation===
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */
numeric digits 30 /*in case user wants bigger nums.*/
Line 397 ⟶ 398:
──────── a Carmichael number: 61 ∙ 271 ∙ 571
──────── 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
| |||