# Mersenne Primes

Mersenne
primes are primes of the form M_{p}=2^{p}-1, where
p is also prime. They were first described by the 17th century French
mathematician Marin Mersenne.

They are of interest due to the following theory by Lucas and Lehmer.

Consider the series

s_{0}=4 s_{n+1}=s_{n}*s_{n}-2

Then if s_{p-2} is divisible by M_{p},
M_{p} is prime.

This is a much faster test than testing all possible factors of
M_{p}, however s_{n} does grow quite rapidly, the
first few terms being 4, 14, 194, 37 634,
1 416 317 954, and the next term will exceed the
range of a 32 bit integer, and the next but one that of a
64 bit integer.

Two things help make this more usable. Firstly the series can be rewritten as:

s_{0}=4 s_{n+1}=(s_{n}*s_{n}-2) mod M_{p}

Then if s_{p-2} is zero, M_{p} is prime.

Secondly, python very unusually can calculate with arbitrarily long integers exactly. Once the integer becomes too large to use one of the CPU's standard types, python switches to a (much slower) emulation of a sufficiently large integer. So whereas writing this in most languages would be painful, in python we can write:

#!/usr/bin/python3 from math import sqrt p=3 while (p<128): # See if p is prime pprime=True for f in range (3,int(sqrt(p))+1,2): if (p%f==0): pprime=False break; if not pprime: p+=2 continue Mp=(1<<p)-1 s=4 for i in range (1,p-1): s=(s*s-2)%Mp if (s==0): prime=True else: prime=False print("p=%3d, 2^p-1=%d"%(p,Mp),end="") if (prime): print(" is prime") else: print(" is not prime") p+=2

That code will print all Mersenne primes found by hand. The last,
2^{127}-1, was found by Lucas in 1876.

M_{127}=2^{127}-1=170,141,183,460,469,231,731,687,303,715,884,105,727

There is quite a gap before the next Mersenne prime, so one might wish to modify the code so that it prints nothing for non-primes. If one sets the limit on the p loop to 3300 it will find all Mersenne primes discovered before 1960, and take a little over a minute to run.

However, this code is not optimal for finding very large Mersenne primes, for there are tricks that can be used to speed up the calculation of the s series considerably. Using these, and raising the limit on p to 11214, results in finding all Mersenne primes found before 1971 in under half an hour. The last one found has over three thousand decimal digits.

(To run the above code:

$ curl -O http://www.sci-pi.org.uk/maths/mersenne.py $ chmod +x mersenne.py $ ./mersenne.py

)