Factors of a Mersenne number: Difference between revisions

 

 

 

These primality tests only work on Mersenne numbers where P is prime. For example, M₄=15 yields no factors using these techniques, but factors into 3 and 5, neither of which fit 2kP+1.

 

 

=={{header|Ada}}==

mersenne.adb:

-- reuse Is_Prime from [[Primality by Trial Division]]

with Is_Prime;

Ada.Text_IO.Put_Line ("is not a Mersenne number");

end;

 

<pre>2 ** 929 - 1 has factor 13007</pre>

 

<!-- {{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

Compiles, but I couldn't maxint not in library, works with manually entered maxint, bits width. Leaving some issue with newline -->

PR READ "prelude/is_prime.a68" PR;

 

FI

 

Example:

<pre>

M +929 has a factor: +13007

</pre>

 

=={{header|AutoHotkey}}==

ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=144 discussion]

MsgBox % MFact(2) ; 0

MsgBox % MFact(3) ; 0

y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1

Return y

=={{header|BBC BASIC}}==

PRINT "A factor of M937 is "; FNmersenne_factor(937)

END

ENDWHILE

= Y%

<pre>A factor of M929 is 13007

A factor of M937 is 28111</pre>

 

=={{header|C}}==

if (n%2==0) return n==2;

if (n%3==0) return n==3;

else break;

} while(1);

 

 

namespace prog

}

}

 

=={{header|CoffeeScript}}==

{{trans|Ruby}}

 

limit = Math.sqrt(Math.pow(2,p) - 1)

k = 1

 

checkMersenne(prime) for prime in ["2","3","4","5","7","11","13","17","19","23","29","31","37","41","43","47","53","929"]

 

<pre>M2 = 2^2-1 is prime

=={{header|Common Lisp}}==

{{trans|Maxima}}

(loop for k from 1

for n = (1+ (* 2 k p))

finally (return n)))

 

 

13007

 

=== Version 2 ===

 

We can use a primality test from the [[Primality by Trial Division#Common_Lisp|Primality by Trial Division]] task.

 

"Is N prime?"

(and (> n 1)

(or (= n 2) (oddp n))

(loop for i from 3 to (isqrt n) by 2

 

Specific to this task, we define modulo-power and mersenne-prime-p.

 

(loop with square = 1

for bit across (format nil "~b" power)

(primep q)

(= 1 (modulo-power 2 power q)))

 

We can run the same tests from the [[#Ruby|Ruby]] entry.

M53 = 2**53-1 is composite with factor 6361.

M929 = 2**929-1 is composite with factor 13007.</pre>

 

=={{header|D}}==

 

if (n < 2 || n % 2 == 0)

return n == 2;

}

 

if ((e & 1) == 1)

result = (result * b) % m;

}

 

immutable ulong q = 2 * p * k + 1;

modPow(2, p, q) == 1)

return q;

}

}

 

void main() {

{{out}}

<pre>Factor of M929: 13007</pre>

 

=={{header|Forth}}==

3

begin 2dup dup * >=

 

929 factor-mersenne . \ 13007

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

IMPLICIT NONE

INTEGER :: exponent, factor

Mfactor = 0

END FUNCTION

M929 has a factor: 13007

=={{header|GAP}}==

end;

 

# If n is not prime, fail immediately

# 3454817

 

MersenneSmallFactor(101);

# fail

 

FactorsInt(2^101-1);

 

=={{header|Go}}==

 

import (

}

return int32(pow)

<pre>

No factors of M31 found.

=={{header|Haskell}}==

 

 

import Control.Monad

import Control.Arrow

map (succ.(2*m*)). enumFromTo 1 $ m `div` 2

bs = int2bin m

 

 

=={{header|J}}==

 

qs=. (#~8&(1=|+.7=|))(#~1&p:)1+(*(1x+i.@<:@<.)&.-:)y

qs#~1=qs&|@(2&^@[**:@])/ 1,~ |.#: y

 

=={{header|Java}}==

import java.math.BigInteger;

 

}

 

<pre>M1 is not prime

M2 is prime

=={{header|JavaScript}}==

 

var limit, k, q

limit = Math.sqrt(Math.pow(2,p) - 1)

f = mersenne_factor(p)

console.log(f == null ? "prime" : "composite with factor "+f)

 

<pre>

</pre>

 

Believe it or not, this type of test runs faster in Mathematica than the squaring version described above.

 

If[Mod[2^44497, i] == 1,

 

=={{header|Maxima}}==

while mod(m, 2 * k * p + 1) # 0 do k: k + 1,

2 * k * p + 1

 

mersenne_fac(929);

 

=={{header|Octave}}==

(GNU Octave has a <code>isprime</code> built-in test)

 

function b = bittst(n, p)

b = bitand(n, 2^(p-1)) > 0;

endfunction

 

 

=={{header|PARI/GP}}==

This version takes about 15 microseconds to find a factor of 2⁹²⁹ &minus; 1.

forstep(q=2*p+1,sqrt(2)<<(p\2),2*p,

[1,0,0,0,0,0,1][q%8] && Mod(2, q)^p==1 && return(q)

1<<p-1

};

 

This implementation seems to be broken:

printp("Test TM \t...");

S=2*p+1;

);

return(status);

 

=={{header|Pascal}}==

{{trans|Fortran}}

 

function isPrime(n: longint): boolean;

else

writeln('M', exponent, ' (2**', exponent, ' - 1) has the factor: ', factor);

<pre>

:> ./FactorsMersenneNumber

 

=={{header|Perl}}==

use utf8;

 

print $f? "M$m = $x = $q × @{[$x / $q]}\n"

: "M$m = $x is prime\n";

M2 = 3 is prime

M3 = 7 is prime

M53 = 9007199254740991 = 6361 × 1416003655831

M59 = 576460752303423487 = 179951 × 3203431780337

 

 

}

 

{{out}}

 

=={{header|PHP}}==

{{trans|D}}

Requires bcmath

 

function mersenneFactor($p) {

}

return true;

 

<pre>M929 has a factor: 13007</pre>

 

=={{header|PicoLisp}}==

(let M 1

(loop

(> N 1)

(bit? 1 N)

 

(de mFactor (P)

(prime? Q)

(= 1 (**Mod 2 P Q)) )

<pre>: (for P (2 3 4 5 7 11 13 17 19 23 29 31 37 41 43 47 53 929)

(prinl

M53 = 2**53-1 is composite with factor 6361

M929 = 2**929-1 is composite with factor 13007</pre>

 

=={{header|Python}}==

 

return True # code omitted - see Primality by Trial Division

 

print "No factor found for M%d" % exponent

else:

<pre>

Enter exponent of Mersenne number: 929

M929 has a factor: 13007

</pre>

 

=={{header|REXX}}==

 

end /*j*/

 

</pre>

 

=={{header|Ruby}}==

 

def mersenne_factor(p)

while (2*k*p - 1) < limit

q = 2*k*p + 1

# q is a factor of 2**p-1

return q

end

nil

end

 

end

 

<pre>M2 = 2**2-1 is prime

M3 = 2**3-1 is prime

M53 = 2**53-1 is composite with factor 6361

M929 = 2**929-1 is composite with factor 13007</pre>

 

=={{header|Scala}}==

 

}

 

 

 

 

 

=={{header|Scheme}}==

This works with PLT Scheme, other implementations only need to change the inclusion.

 

#lang scheme

 

(= 1 (modpow p i))))

i))

<pre>

> (mersenne-factor 929)

 

=={{header|Seed7}}==

 

const func boolean: isPrime (in integer: number) is func

begin

writeln("Factor of M929: " <& mersenneFactor(929));

 

Original source: [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime],

[http://seed7.sourceforge.net/algorith/math.htm#modPow modPow] (modified to use integer instead of bigInteger).

 

<pre>

Factor of M929: 13007

</pre>

 

=={{header|Tcl}}==

For <code>primes::is_prime</code> see [[Prime decomposition#Tcl]]

binary scan [binary format I1 $n] B* binstring

return [split [string trimleft $binstring 0] ""]

} else {

puts "no factor found for M$exp"