Factors of a Mersenne number: Difference between revisions
Content added Content deleted
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
(add RPL) |
||
Line 2,739: | Line 2,739: | ||
A factor of M937 is 28111 |
A factor of M937 is 28111 |
||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
{{works with|HP|48}} |
|||
<code>PRIM?</code> is defined at [[Primality by trial division#RPL|Primality by trial division]] |
|||
{| class="wikitable" ≪ |
|||
! RPL code |
|||
! Comment |
|||
|- |
|||
| |
|||
≪ SWAP R→B → quotient power |
|||
≪ 2 power B→R LN 2 LN / FLOOR ^ R→B |
|||
1 |
|||
'''WHILE''' OVER B→R '''REPEAT''' |
|||
SQ |
|||
'''IF''' OVER power AND B→R '''THEN''' DUP + '''END''' |
|||
quotient MOD |
|||
SWAP SR SWAP |
|||
'''END''' SWAP DROP |
|||
≫ ≫ '<span style="color:blue">MODPOW</span>' STO |
|||
≪ 2 OVER ^ 1 - √ 0 → power max k |
|||
≪ 1 |
|||
'''WHILE''' 'k' INCR 2 * 1 + DUP max ≤ '''REPEAT''' |
|||
'''IF''' { 1 7 } OVER 8 MOD POS THEN |
|||
'''IF''' DUP <span style="color:blue">PRIM?</span> THEN |
|||
'''IF''' power OVER <span style="color:blue">MODPOW</span> 1 == '''THEN''' |
|||
SWAP max 'k' STO '''END''' |
|||
'''END END''' |
|||
DROP |
|||
'''END''' DROP |
|||
≫ '<span style="color:blue">MFACT</span>' STO |
|||
| |
|||
<span style="color:blue">MODPOW</span> ''( power quotient → remainder )'' |
|||
create top-bit mask |
|||
square = 1 |
|||
while mask is not zero |
|||
square *= square |
|||
if unmasked bit = 1 then square += square |
|||
square = square mod quotient |
|||
shift mask right |
|||
clean stack |
|||
return square |
|||
<span style="color:blue">MFACT</span> ''( N → factor ) '' |
|||
factor = 1 |
|||
while 2k+1 ≤ sqrt(M(N)) |
|||
if 2k+1 mod 8 is equal to 1 or 7 |
|||
if 2k+1 prime |
|||
is 2K+1 a factor of M(N) ? |
|||
if yes, exit loop |
|||
return factor |
|||
|} |
|||
929 <span style="color:blue">MFACT</span> |
|||
{{out}} |
|||
<pre> |
|||
1: 13007 |
|||
</pre> |
|||
Factor found in 69 minutes on a 4-bit HP-48SX calculator. |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |