Mersenne Primes and Perfect Numbers

Primes are a fascinating group of integer numbers. They definition is short and clear (a prime number is a number that can be divided without remainder only by itself and 1), there are infinite primes and “quite frequent” (for number of n digits they are about n/(log n), so one number every log n is prime).

Yet it is hard to prove deterministically the primality for a number of a large size, since algorithms have a polynomial execution time like O(x⁵), so also a number of 70-80.000 digits is hard to prove prime.

This is not true for Mersenne Primes.

Mersenne Primes

Mersenne Primes are prime numbers that are one unit smaller than a power of two; in general a Mersenne Number is a number with this form:

M_k = 2^k – 1

and Mersenne Primes are the special case where both k and M_k are primes.

The first Mersenne Primes are:

2²-1 = 3

2³-1 = 7

2⁵-1 = 31

2⁷-1 = 127

2¹³-1 = 8191

2¹¹-1 = 2047 = 23 * 89 is the first composite Mersenne Number with k prime, but in general as k grows Mersenne Prime become very sparse. Here the first 20 exponents:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423

It is easy to show that is k is not prime then M_k is not prime, in fact if k=ab:

\[ M_{ab} = 2^{ab} – 1 = (2^a – 1)(2^{(b-1)a} + 2^{(b-2)a} + \ldots + 2^a + 1) \]

Please note that in base 2 M_k is just k “1” in a row. (3₁₀ = 11₂, 7₁₀ = 111_2, etc).

2	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229
233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349
353	359	367	373	379	383	389	397	401	409
419	421	431	433	439	443	449	457	461	463
467	479	487	491	499	503	509	521	523	541

Lucas-Lehmer Primality Test

Why is less hard to prove primality of these numbers? Because there is a particularly efficient primality test available for them: Lucas-Lehmer primality test. Please refer to Wikipedia for the algorithm, the important thing is that to prove primality of M_p = 2^p-1= n it is performed a cycle of about p iteration (that is logarithmic in M_p (log n)), that perform multiplication of numbers (mod M_p) (so with size O(n). Ordinary multiplication would require O(n²) operations for the multiplication, but using Fast Fourier Transform-based algorithms like Schönhage–Strassen algorithm we can compute it in O(n log n log log n), so the total complexity is O(n (log n)² log log n), tremendously faster than general purpose algorithms. In fact Mersenne primes hold the record of largest known primes since decades, the actually largest known prime is 2^82589933 − 1.

Actually only 51 Mersenne Primes have been found, mainly thanks to the GIMPS, a project that search Mersenne Primes during idle time of computers that join the project. It is unknown if they are infinite or if it exists a formula to easily find them.

Perfect numbers

An interesting fact about Mersenne Primes is that they related to even perfect numbers. A perfect number is a number equal to the sum of its positive divisor except the number itself (e.g. 6 = 1+2+3, 28=1+2+3+4+7+14).

Euclid proved that is 2^p-1 is prime than (2^p-1)2^p-1 is perfect (this is easy, 2^p-1 has factors 1 and 2^p-1, while 2^p-1 has all the 2 powers from 0 to p-1, just combine and sum them). Moreover Euler proved that all the even perfect number have this form.

The situation is still uncertain for odd perfect numbers. So far we don’t know if any exists, however some interesting fact is known, for example they should have at list 1500 digits and 10 different factors.

Some open questions

Here some open questions more or less related to Mersenne Primes that deserve attentions if you like Mathematics.

Are there infinite many Mersenne Primes?

Are there a formula to compute nth Mersenne Prime?

Does exist an odd perfect number?

Now let’s raise the bar: consider the sequence of Mersenne Primes: 2, 3, 7, 127, they are each the exponent of the subsequent number:

• s₁= 2²-1 = 3
• s₂ = 2^s₁-1 = 2³-1 = 7
• s₃ = 2^s₂-1 = 2⁷-1 = 127
• s₄ = 2^s₃-1 = 2¹²⁷-1 about 1.7 * 10³⁸

Is 2^s₄ – 1 prime? Is this the start of a sequence of prime numbers?

Conclusions

This is just an introduction to the argument, I would like to write a post on the Schönhage–Strassen multiplication to use in a Lucas-Lehmer primality test implementation (probably preceded by a FFT post in code optimization section) and waste some time of mine on the above questions, but for now I just wanted to put this down as starting point.