Mersenne primes

Mersenne primes are prime numbers of the form

2 p  −  1

, where

p

is necessarily a prime number (so these are prime Mersenne numbers). For example, 127 is a Mersenne prime since 2 7  −  1 = 127. The largest known Mersenne prime tends to also be the largest known prime number. Currently, the largest known Mersenne prime is 2 77232917  −  1 and has in excess of 23 million decimal digits.

Theorem.

For a number of the form

2 n  −  1

to be prime, it is a necessary condition that

n

be prime. This is to say that if

n

is composite, then so is

2 n  −  1

.

Proof. Consider the powers of 2 modulo a number of the form

2 n  −  1

: we have

1, 2, 4, 8, ..., 2 n   −  2, 2 n   −  1, 1, 2, 4, 8, ...

and so on and so forth, showing that an instance of 1 is encountered periodically at every

n

doubling steps. This means that for any positive integer

m

, the congruence

2 m n   ≡   1  (mod 2 n  −  1)

holds and therefore the number

2 m n  −  1

is divisible by

2 n  −  1

(for example, every fourth Mersenne number starting with 15 is divisible by 15: 255, 4095, 65535, 1048575, etc.). If

n

is composite, it must have at least one divisor apart from 1 and itself, and therefore

2 n  −  1

has at least one divisor that is also a Mersenne number (with the exponent corresponding to that divisor of

n

), thus proving that

2 n  −  1

is also composite. But if

n

is prime, then

2 n  −  1

is divisible by no Mersenne numbers other than 1 and itself, and is thus potentially prime. □

The condition is necessary but not sufficient, and to prove the lack of sufficiency you might be satisfied by the example of 2 11  −  1 = 2047 = 23  ×  89 = (2  ×  11 + 1)  ×  (8  ×  11 + 1).

It is not known whether the set of Mersenne primes is finite or infinite. The Lenstra–Pomerance–Wagstaff conjecture asserts that, on the contrary, there are infinitely many Mersenne primes and predicts their order of growth. There have been less than 50 identified through 2011.

Mersenne primes are interesting for their connection to even perfect numbers. In the 4^th century bc, Euclid demonstrated that if

M p

is a Mersenne prime then

2 p  − 1 ⋅  (2 p − 1) = Mp + 1 2  ⋅  Mp

is an even perfect number. In the 18^th century, Leonhard Euler proved that, conversely, all even perfect numbers have this form.

Base 2 repunits

The base 2 repunits (sometimes called Mersenne numbers, although that name usually applies to the next definition) are numbers of the form

R (2) n :=   n  − 1 ∑   i   = 0    1 ⋅  2 i = 2 n − 1 2 − 1 = 2 n − 1, n ≥ 0.

Generating function of base 2 repunits

The ordinary generating function of base 2 repunits is

G{R (2) n}(x) ≡   ∞ ∑   n   = 0    R (2) n x n = x (1 − 2 x) (1 − x) .

Exponential generating function of base 2 repunits

The exponential generating function of base 2 repunits is

E{R (2) n  − 1}(x) ≡   ∞ ∑   n   = 1    R (2) n −1 x n n! = (e  x − 1) 2 2 .

Sequences

A000225

2 n  −  1, n   ≥   0

. (Base 2 repunits, sometimes called Mersenne numbers, although that name is usually reserved for A001348.)

{0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, ...}

A001348 The Mersenne numbers:

M p = 2 p  −  1

, where

p

is prime.

{3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, 137438953471, 2199023255551, 8796093022207, 140737488355327, 9007199254740991, 576460752303423487, ...}

A000668 The Mersenne primes (of form

M p = 2 p  −  1

where

p

is necessarily a prime).

{3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727, ...}

A117293 The Mersenne primes written in binary.

{11, 111, 11111, 1111111, 1111111111111, 11111111111111111, 1111111111111111111, 1111111111111111111111111111111, 1111111111111111111111111111111111111111111111111111111111111, ...}

A000043 Mersenne exponents: primes

p

such that

M p = 2 p  −  1

is prime. The number of digits (base 2) in

Mp

.

{2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, ...}

A028335 The number of digits (base 10) in

n

th Mersenne prime.

{1, 1, 2, 3, 4, 6, 6, 10, 19, 27, 33, 39, 157, 183, 386, 664, 687, 969, 1281, 1332, 2917, 2993, 3376, 6002, 6533, 6987, 13395, 25962, 33265, 39751, 65050, 227832, 258716, 378632, 420921, 895932, ...}

A061652 Even superperfect numbers:

2 ( p   − 1)

where

2 p  −  1

is a Mersenne prime (A000043 and A000668).

{2, 4, 16, 64, 4096, 65536, 262144, 1073741824, 1152921504606846976, 309485009821345068724781056, 81129638414606681695789005144064, 85070591730234615865843651857942052864, ...}

A138837 Primes that are not Mersenne primes (A000668).

{2, 5, 11, 13, 17, 19, 23, 29, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, ...}

Decimal expansions of the n-th Mersenne prime

The GIMPS project maintains a ranked list of the known Mersenne primes. The ranking is double-checked for most numbers in the list, except for a few found in the last five years. The list has all details like date of discovery, discovered by, number of digits etc.

In the last decades Mersenne primes with millions of digits were found, and the full decimal representations occupy megabytes, therefore they are not suitable for OEIS b-files. Maximilian Hasler gave a PARI program which computes some number of leading digits directly:

A193864_list(Nmax)={default(realprecision, Nmax+5); 
digits(10^frac(43112609*log(2)/log(10))\.1^Nmax)} 
\\ Use digits(x)=eval(Vec(Str(x))) in older PARI versions.
A193864_list(105)

There is a Perl program which reads A000043 and writes all known Mersenne primes numbers in less than a minute, with the aid of tiny PARI programs like:

 write("a089578.txt", 2^20996011 - 1); quit;

The program generates a list of the OEIS sequences for decimal expansions of Mersenne primes:

Rank	2^p-1 A000043	OEIS A-number	# of digits A028335	First 16 digits A135613, A138862, A138864	Last 16 digits A080172, A080173, A138865
1	2	A000668	1	3	3
2	3	A000668	1	7	7
3	5	A000668	2	31	31
4	7	A000668	3	127	127
5	13	A000668	4	8191	8191
6	17	A000668	6	131071	131071
7	19	A000668	6	524287	524287
8	31	A000668	10	2147483647	2147483647
9	61	A000668	19	2305843009213693	5843009213693951
10	89	A000668	27	6189700196426901	2690137449562111
11	107	A000668, A169684	33	1622592768292133	3391578010288127
12	127	A000668, A169681	39	1701411834604692	7303715884105727
13	521	A000668, A169685	157	6864797660130609	4028291115057151
14	607	A000668, A204063	183	5311379928167670	5393219031728127
15	1279	A000668, A248931	386	1040793219466439	0555703168729087
16	2203	A000668, A248932	664	1475979915214180	9497686697771007
17	2281	A000668, A248933	687	4460875571837584	3172418132836351
18	3217	A000668, A248934	969	2591170860132026	0677362909315071
19	4253	A248935	1281	1907970075244390	4687815350484991
20	4423	A248936	1332	2855425422282796	1057902608580607
21	9689	A275977	2917	4782202788054612	2696826225754111
22	9941	A275979	2993	3460882824908512	6224883789463551
23	11213	A275980	3376	2814112013697373	1476087696392191
24	19937	A275981	6002	4315424797388162	1539030968041471
25	21701	A275982	6533	4486791661190433	0828353511882751
26	23209	A275983	6987	4028741157789887	3355523779264511
27	44497	A275984	13395	8545098243036338	7686961011228671
28	86243		25962	5369279955027563	7021709433438207
29	110503		33265	5219283133417550	1621083465515007
30	132049		39751	5127402762693207	8578455730061311
31	216091		65050	7460931030646613	6204103815528447
32	756839		227832	1741359068200870	3793328544677887
33	859433		258716	1294981256042076	4267243500142591
34	1257787		378632	4122457736214286	7188976089366527
35	1398269		420921	8147175644125730	2025868451315711
36	2976221		895932	6233400762485786	6256743729201151
37	3021377		909526	1274116830300933	2631973024694271
38	6972593		2098960	4370757441270813	6526142924193791
39	13466917	A089065	4053946	9249477380067013	3855470256259071
40	20996011	A089578	6320430	1259768954503301	4065762855682047
41	24036583		7235733	2994104294041571	6921882733969407
42	25964951		7816230	1221646300612779	3257280577077247
43	30402457	A117853	9152052	3154164756188460	4297411652943871
44	32582657		9808358	1245750260153694	2880154053967871
45	37156667		11185272	2022544068909773	0265022308220927
46	42643801		12837064	1698735164527416	1954765562314751
47	43112609	A193864	12978189	3164702693302559	2181166697152511

See also

• Perfect numbers
• Fermat primes

External links

• Great Internet Mersenne Prime Search (GIMPS)
• Pablo A. Panzone, On the generating functions of Mersenne and Fermat primes, Springer Link, 2010.
• Pablo A. Panzone, On the generating functions of Mersenne and Fermat primes, Collectanea, 2010.