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|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}}==

 

 

 

 

"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}}==

 

}

 

}

}

 

}

}

 

void main() {

 

=={{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|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

 

 

 

 

 

 

<pre>

</pre>

 

=={{header|Java}}==

import java.math.BigInteger;

 

}

 

<pre>M1 is not prime

M2 is prime

</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|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|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

</pre>

 

 

 

 

 

 

 

 

 

 

Output:

</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|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)

#f

</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"