Mersenne primes are
prime numbers of the form
, where
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.
[1]
Theorem.
For a number of the form to be prime, it is a necessary condition that be prime. This is to say that if is composite, then so is .
Proof. Consider the powers of 2 modulo a number of the form : 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 doubling steps. This means that for any positive integer , the congruence holds and therefore the number is divisible by (for example, every fourth Mersenne number starting with 15 is divisible by 15: 255, 4095, 65535, 1048575, etc.). If is composite, it must have at least one divisor apart from 1 and itself, and therefore has at least one divisor that is also a Mersenne number (with the exponent corresponding to that divisor of ), thus proving that is also composite. But if is prime, then 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
is a Mersenne prime then
-
2 p − 1 ⋅ (2 p − 1) = ⋅ 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 := 1 ⋅ 2 i = = 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) ≡ R (2) n x n = . |
Exponential generating function of base 2 repunits
The exponential generating function of base 2 repunits is
-
E{R (2) n − 1}(x) ≡ R (2) n −1 = . |
Sequences
A000225 . (
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:
, where
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
where
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
such that
is
prime. The number of digits (base
2) in
.
-
{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
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:
where
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
Notes
External links