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
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.
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 Mp=2p-1 rules out more than just two as a potential factor, see factors of Mersenne numbers.