Factors of a Mersenne number: Difference between revisions

Content added Content deleted
m (added a ;See also: section header.)
m (→‎{{header|REXX}}: simplified program, optimized a function, added wording to the REXX section header..)
Line 2,259: Line 2,259:


=={{header|REXX}}==
=={{header|REXX}}==
REXX practically has no limit on the number of decimal digits (precision).
REXX practically has no limit (well, up to around 8 million) on the number of decimal digits (precision).
<lang rexx>/*REXX program uses exponent─and─mod operator to test possible Mersenne numbers. */
<lang rexx>/*REXX program uses exponent─and─mod operator to test possible Mersenne numbers. */
numeric digits 500 /*dealing with some ginormous numbers. */
numeric digits 20 /*this will be increased if necessary. */
⚫
do j=1 to 61; z=j /*process a range, & then do one more #*/

do j=1 to 61; z=j /*when J reaches 61, Z turns into 929.*/
if z==61 then z=929 /*now, a switcheroo, Z turns into 929*/
⚫
if z==61 then z=929 /*now, a switcheroo, 61 turns into 929.*/
if \isPrime(z) then iterate /*if Z isn't a prime, keep plugging.*/
if \isPrime(z) then iterate /*if Z isn't a prime, keep plugging.*/
r=testMer(z) /*If Z is prime, give Z the 3rd degree.*/
r=testMer(z) /*If Z is prime, give Z the 3rd degree.*/
Line 2,280: Line 2,279:
iSqrt: procedure; parse arg x; #=1; r=0; do while #<=x; #=#*4; end
iSqrt: procedure; parse arg x; #=1; r=0; do while #<=x; #=#*4; end
do while #>1; #=#%4; _=x-r-#; r=r%2; if _>=0 then do; x=_; r=r+#; end
do while #>1; #=#%4; _=x-r-#; r=r%2; if _>=0 then do; x=_; r=r+#; end
end /*while*/
end /*while*/ /*iSqrt ≡ integer square root.*/
return r /*───── ─ ── ─ ─ */
return r
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
modPow: procedure; parse arg base,n,div; sq=1; $=x2b( d2x(n) ) + 0
modPow: procedure; parse arg base,n,div; sq=1; $=x2b( d2x(n) ) + 0
Line 2,289: Line 2,288:
return sq
return sq
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
testMer: procedure; parse arg x /*test a possible Mersenne prime.*/
testMer: procedure; parse arg x; p=2**x /* [↓] do we have enough digits?*/
sqRoot=iSqrt(2**x) /*iSqrt ≡ integer square root.*/
if pos('E',p)\==0 then do; parse var p 'E' _; numeric digits _+2; p=2**x; end
/*───── ─ ── ─ ─ */
!.=1; !.1=0; !.7=0 /*array used for a quicker test. */
do k=1; q=2*k*x + 1 /* _____ */
R=iSqrt(p) /*obtain integer square root of P*/
if q>sqRoot then return 0 /*Is q>√ 2^x ? A Mersenne prime*/
do k=1; q=2*k*x + 1 /* _____ */
_=q // 8 /*obtain the remainder when ÷ 8. */
if q>R then return 0 /*Is q>√ 2^x ? A Mersenne prime*/
if _\==1 & _\==7 then iterate /*must be either one or seven.*/
m=q // 8 /*obtain the remainder when ÷ 8. */
if \isPrime(q) then iterate /*Q ¬prime? Then keep on looking.*/
if !.m then iterate /*M must be either one or seven.*/
if modPow(2,x,q)==1 then return q /*Not a prime? Return a factor.*/
if modPow(2,x,q)==1 then return q /*Not a prime? Return a factor.*/
end /*k*/</lang>
end /*k*/</lang>
Program note: &nbsp; the &nbsp; '''iSqrt''' &nbsp; function computes the integer square root of a non-negative integer without using any floating point, just integers.
Program note: &nbsp; the &nbsp; '''iSqrt''' &nbsp; function computes the integer square root of a non-negative integer without using any floating point, just integers.


Retrieved from "https://rosettacode.org/wiki/Factors_of_a_Mersenne_number"