This site is supported by donations to The OEIS Foundation.

Mersenne primes

From OeisWiki
(Redirected from Mersenne prime)
Jump to: navigation, search
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.[1]
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 4th 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

Notes

  1. ↑ https://www.mersenne.org/

External links

Retrieved from "https://oeis.org/w/index.php?title=Mersenne_primes&oldid=1628693"