Perfect numbers: Difference between revisions
Content added Content deleted
(→traditional method: replaced with the appropriate REXX program.) |
m (→Lucas-Lehmer + other optimizations: changed indentations in the isPerfect function.) |
||
| Line 1,858: | Line 1,858: | ||
===Lucas-Lehmer + other optimizations=== |
===Lucas-Lehmer + other optimizations=== |
||
This version uses the Lucas-Lehmer method, digital |
This version uses the Lucas-Lehmer method, digital roots, and restricts itself to ''even'' numbers, and |
||
<br>also utilizes a check for the last-two-digits as per François Édouard Anatole Lucas (in 1891). |
<br>also utilizes a check for the last-two-digits as per François Édouard Anatole Lucas (in 1891). |
||
| Line 1,882: | Line 1,882: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
isPerfect: procedure expose @. !. ? /*expose (make global) some variables. */ |
isPerfect: procedure expose @. !. ? /*expose (make global) some variables. */ |
||
parse arg x 1 y '' -2 ? /*# (and copy), and the last 2 digits.*/ |
|||
if x==6 then return 1 /*handle the special case of six. */ |
|||
if !.?==2 then return 0 /*test last two digits: François Lucas.*/ |
|||
/*╔═════════════════════════════════════════════╗ |
|||
/*╔════════════════════════════════════════════════════════════════════════════════════╗ |
|||
║ Lucas─Lehmer know that perfect numbers can ║ |
|||
║ Lucas─Lehmer know that perfect numbers can be expressed as: [2^n -1] * {2^(n-1) } ║ |
|||
║ be expressed as: [2^n -1] * {2^(n-1) } ║ |
|||
╚════════════════════════════════════════════════════════════════════════════════════╝*/ |
|||
╚═════════════════════════════════════════════╝*/ |
|||
if @.0<x then do @.1=@.1 while @._ <= x; _=(2**@.1-1)*2**(@.1-1); @.0=_; @._=_ |
|||
if @.0<x then do @.1=@.1 while @._<=x; _=(2**@.1-1)*2**(@.1-1); @.0=_; @._=_ |
|||
end /*@.1*/ /* [↑] uses memoization for formula. */ |
|||
if @.x==0 then return 0 /*Didn't pass Lucas-Lehmer? Not perfect*/ |
|||
/*[↓] perfect numbers digital root = 1*/ |
/*[↓] perfect numbers digital root = 1*/ |
||
do until y<10 /*find the digital root of Y. */ |
|||
parse var y d 2; do k=2 for length(y)-1; |
parse var y d 2; do k=2 for length(y)-1; d=d+substr(y,k,1); end /*k*/ |
||
y=d /*find digital root of the digital root*/ |
|||
end /*until*/ /*wash, rinse, repeat ··· */ |
|||
if d\==1 then return 0 /*Is digital root ¬ 1? Then ¬ perfect.*/ |
|||
s=3 + x%2 /*we know the following factors: unity,*/ |
|||
z=x /*2, and x÷2 (x is even). */ |
|||
q=1; do while q<=z; q=q*4; end /*while q≤z*/ |
q=1; do while q<=z; q=q*4 ; end /*while q≤z*/ /* _____*/ |
||
r=0 /* [↓] R will be the integer √ X */ |
|||
r=0 |
|||
do while q>1; q=q%4; |
do while q>1; q=q%4; _=z-r-q; r=r%2; if _>=0 then do; z=_; r=r+q; end |
||
end /*while q>1*/ /* [↑] compute the integer SQRT of X.*/ |
|||
/* |
/* _____*/ |
||
do j=3 to r until s>x |
do j=3 to r until s>x /*starting at 3, find factors ≤ √ X */ |
||
if x//j==0 then s=s+j+x%j |
if x//j==0 then s=s+j+x%j /*J divisible by X? Then add J and X÷J*/ |
||
end /*j*/ |
end /*j*/ |
||
return s==x /*if the sum matches X, then perfect! */</lang> |
|||
'''output''' is the same as the traditional version and is about '''500''' times faster (testing 34,000,000 numbers). <br><br> |
'''output''' is the same as the traditional version and is about '''500''' times faster (testing 34,000,000 numbers). <br><br> |
||