# Mersenne Primes

Mersenne primes are primes of the form Mp=2p-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

```  s0=4
sn+1=sn*sn-2
```

Then if sp-2 is divisible by Mp, Mp is prime.

This is a much faster test than testing all possible factors of Mp, however sn 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:

```  s0=4
sn+1=(sn*sn-2) mod Mp
```

Then if sp-2 is zero, Mp 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, 2127-1, was found by Lucas in 1876.

```M127=2127-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
```

)