Factors of a Mersenne number: Difference between revisions

* &nbsp; [https://www.youtube.com/watch?v=SNwvJ7psoow Computers in 1948: 2¹²⁷ - 1] <br> &nbsp; &nbsp; &nbsp; (Note: &nbsp; This video is no longer available because the YouTube account associated with this video has been terminated.)

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

#include <cstdint>

 

typedef uint64_t integer;

integer bit_count(integer n) {

integer count = 0;

n >>= 1;

return count;

}

integer mod_pow(integer p, integer n) {

integer square = 1;

square <<= 1;

}

return square;

if (n % 2 == 0)

return n == 2;

if (n % p == 0)

return false;

return true;

}

 

integer find_mersenne_factor(integer p) {

}

return 0;

 

int main() {

return 0;

 

{{out}}

{{trans|Python}}

 

(:gen-class))

 

:let [s (-main p)]]

(println s))

{{Output}}

<pre>

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

=={{header|Crystal}}==

{{trans|Ruby}}

 

def prime?(n) # P3 Prime Generator primality test

 

(2..53).each { |p| check_mersenne(p) if prime?(p) }

 

{{out}}

 

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

{{trans|Ruby}}

def mersenne_factor(p) do

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

 

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,929]

 

{{out}}

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>

 

=={{header|Factor}}==

math math.bits math.functions math.primes sequences ;

IN: rosetta-code.mersenne-factors

[ [I No factor found for M${}.I] ] if* nl ;

 

{{out}}

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

{{trans|C}}

 

Function isPrime(n As Integer) As Boolean

Print

Print "Press any key to quit"

 

{{out}}

2^97 - 1 = 0 (mod 11447)

2^929 - 1 = 0 (mod 13007)

</pre>

 

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

 

=={{header|Julia}}==

 

using Primes

if mf != -1 println("M$i = ", mf, " × ", (big(2) ^ i - 1) ÷ mf)

else println("M$i is prime") end

 

{{out}}

=={{header|Kotlin}}==

{{trans|C}}

 

fun isPrime(n: Int): Boolean {

}

}

 

{{out}}

 

=={{header|Lingo}}==

bits = getBits(e)

sq = 1

end repeat

return bits

 

if modPow(2, 929, i)=1 then

put "M929 has a factor: " & i

exit repeat

end if

 

{{out}}

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

=={{header|Phix}}==

Translation/Amalgamation of BBC BASIC, D, and Go

{{Out}}

<pre>

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

 

=={{header|Prolog}}==

mersenne_factor(P, F) :-

prime(P),

N mod D =\= 0,

D2 is D + A, prime(N, D2, As).

{{Out}}

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

(formerly Perl 6)

 

my @bits = $bits.base(2).comb;

loop (my $sq = 1; @bits; $sq %= $p) {

}

$sq == 1;

 

for flat 2 .. 60, 929 -> $m {

my $f = 0;

my $x = 2**$m - 1;

my $q;

for 1..* -> $k {

}

 

say $f ?? "M$m = $x\n\t= $q × { $x div $q }"

!! "M$m = $x is prime";

{{out}}

<pre>M2 = 3 is prime

 

This REXX version automatically adjusts the &nbsp; '''numeric digits''' &nbsp; to whatever is needed.

numeric digits 20 /*this will be increased if necessary. */

parse arg N spec /*obtain optional arguments from the CL*/

end /*until*/

if sq==1 then return q /*Not a prime? Return a factor.*/

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.

 

 

=={{header|Ring}}==

# Project : Factors of a Mersenne number

 

end

return y

Output:

<pre>

A factor of M937 is 28111

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

/** Find factors of a Mersenne number

*

(primes takeWhile (_ <= 97)) ++ List(929, 937) foreach { p => { // Needs some intermediate results for nice formatting

val nMersenne = mersenne(p);

val preAmble = f"${s"M${p}"}%4s = 2^$p%03d - 1 = ${lit}%s"

 

}

}

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

var bits = b.base(2).digits

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

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

: "M#{m} is prime")

{{out}}

<pre>

=={{header|Swift}}==

 

 

extension BinaryInteger {

 

print(mFactor(exp: 929)!)

 

{{out}}

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

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

 

=={{header|zkl}}==

{{trans|EchoLisp}}

 

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

}

False

m_divisor(4423).println(); // False

{{out}}

<pre>