Factors of a Mersenne number: Difference between revisions

Use the result of the modulo from the last step as the initial value of <tt>square</tt> in the next step:

 

 

Since 2²³ mod 47 = 1, 47 is a factor of 2^P-1.

Using the above method find a factor of 2⁹²⁹-1 (aka M929)

 

<br><br>

 

=={{header|360 Assembly}}==

Use of bitwise operations

(TM (Test under Mask), SLA (Shift Left Arithmetic),SRA (Shift Right Arithmetic)).

MERSENNE CSECT

USING MERSENNE,R15

PG DS CL24 buffer

YREGS

{{out}}

<pre>

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

 

{{out}}

<!-- {{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%

{{out}}

<pre>A factor of M929 is 13007

 

=={{header|Bracmat}}==

= square P divisor highbit log 2pow

. !arg:(?P.?divisor)

| out$"no divisors found"

)

{{out}}

<pre>found some divisors of 2^!P-1 : 13007 and 348890248924938259750454781163390930305120269538278042934009621348894657205785

 

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

 

 

{{out}}

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

 

ulong mersenneFactor(in ulong p) pure nothrow @nogc {

void main() {

writefln("Factor of M929: %d", 929.mersenneFactor);

{{out}}

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

 

=={{header|EchoLisp}}==

;; M = 2^P - 1 , P prime

;; look for a prime divisor q such as : q < √ M, q = 1 or 7 modulo 8, q = 1 + 2kP

→ #t

 

 

=={{header|Erlang}}==

The modpow function is not my original. This is a translation of python, more or less.

 

-module(mersene2).

-export([prime/1,modpow/3,mf/1]).

false -> divisors(N, C-1)

end.

{{out}}

<pre>

M929 is composite with Factor: 13007

[ok,ok,ok,ok,ok,ok,ok]

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

{{out}}

M929 has a factor: 13007

 

=={{header|GAP}}==

local k, m, d;

if IsPrime(n) then

 

FactorsInt(2^101-1);

 

=={{header|Go}}==

 

import (

}

return int32(pow)

{{out}}

<pre>

Using David Amos module Primes [https://web.archive.org/web/20121130222921/http://www.polyomino.f2s.com/david/haskell/codeindex.html] for prime number testing:

 

import HFM.Primes (isPrime)

import Control.Monad

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

bs = int2bin m

 

 

=={{header|Icon}} and {{header|Unicon}}==

 

The following works in both languages:

p := integer(A[1]) | 929

write("M",p," has a factor ",mfactor(p))

}

return

 

Sample runs:

=={{header|J}}==

 

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

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

 

{{out|Examples}}

Empty output --> No factors found.

 

=={{header|Java}}==

import java.math.BigInteger;

 

}

 

{{out}}

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

{{trans|C}}

 

proc isPrime(a: int): bool =

if i != 1: d += 2 * q

else: break

{{out}}

<pre>2^929 - 1 = 0 (mod 13007)</pre>

(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);

{{out}}

<pre>

 

=={{header|Perl}}==

use utf8;

 

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

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

{{out}}

<pre>M2 = 3 is prime

 

Following the task introduction, this uses GMP's modular exponentiation and simple probable prime test for the small numbers, then looks for small factors before doing a Lucas-Lehmer test. For ranges above about p=2000, looking for small factors this way saves time (the amount of testing should be adjusted based on the input size and platform -- this example just uses a fixed amount). Note as well that the Lucas-Lehmer test shown here is ignoring the large speedup we can get by optimizing the modulo operation, but that's a different task.

 

# Use GMP's simple probable prime test.

print "M$p is ", is_mersenne_prime($p) ? "prime" : "composite", "\n";

}

{{out}}

<pre>

</pre>

 

 

=={{header|PHP}}==

{{trans|D}}

Requires bcmath

 

function mersenneFactor($p) {

}

return true;

 

{{out}}

 

=={{header|PicoLisp}}==

(let M 1

(loop

(prime? Q)

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

{{out}}

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

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:

 

{{out|Example}}

 

=={{header|Racket}}==

#lang racket

 

(mersenne-factor 929)

{{out}}

13007

 

 

=={{header|REXX}}==

 

end /*j*/

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.

 

<pre>

</pre>

 

=={{header|Ruby}}==

{{works with|Ruby|1.9.3+}}

 

def mersenne_factor(p)

 

Prime.each(53) { |p| check_mersenne p }

 

{{out}}

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

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

 

=={{header|Scala}}==

 

===Full-blown version===

*

*

*/

 

val two: BigInt = 2

// An infinite stream of primes, lazy evaluation and memo-ized

 

 

def factorMersenne(p: Int): Option[Long] = {

 

// Build a stream of factors from (2*p+1) step-by (2*p)

 

// Limit and Filter Stream and then take the head element

e.headOption

}

 

// Test

 

 

 

}

}

{{out}}

<pre style="height:40ex;overflow:scroll"> M2 = 2^002 - 1 = 3 is a Mersenne prime number. (63 msec)

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

 

#lang scheme

 

(= 1 (modpow p i))))

i))

{{out}}

<pre>

 

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

 

=={{header|Sidef}}==

for (var sq = 1; bits; sq %= p) {

}

sq == 1

}

 

var f = 0

var x = (2**m - 1)

var q

q = (2*k*m + 1)

q%8 ~~ [1,7] || q.is_prime || next

q*q > x || (f = mtest(m, q)) && break

say (f ? "M#{m} is composite with factor #{q}"

: "M#{m} is prime")

{{out}}

<pre>

M929 is composite with factor 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"

 

=={{header|TI-83 BASIC}}==

{{works with|TI-83 BASIC|TI-84Plus 2.55MP}}

The program uses the new remainder function from OS 2.53MP, if not available it can be replaced by:

1→K:0→T

While K≤2^20 and T=0

End

If T=0:0→F

{{in}}

<pre>

 

=={{header|uBasic/4tH}}==

Print "A factor of M937 is "; FUNC(_FNmersenne_factor(937))

 

Next

 

{{out}}

<pre>A factor of M929 is 13007

 

0 OK, 0:123</pre>

=={{header|VBScript}}==

{{trans|REXX}}

for i=1 to 59

z=i

loop

testM=0

{{out}}

<pre>

{{trans|BBC BASIC}}

{{works with|Visual Basic|VB6 Standard}}

Dim q As Long, k As Long, p As Long, d As Long

Dim factor As Long, i As Long, y As Long, z As Long

okfactor:

Debug.Print "M" & q, "factor=" & factor

{{Out}}

<pre>

M47 factor=2351

</pre>