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

  s0=4
  sn+1=sn*sn-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:

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

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¹²⁷-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

)

Testing all possible factors of a Mersenne number is certainly slow, but the construction M_p=2^p-1 rules out more than just two as a potential factor, see factors of Mersenne numbers.