This site is supported by donations to The OEIS Foundation.

Mersenne primes

From OeisWiki

Jump to: navigation, search

This article needs more work.

Please help by expanding it!


Mersenne primes are prime numbers of the form 2p − 1, where p is necessarily a prime number (so these are prime Mersenne numbers). For example, 127 is a Mersenne prime since 27 − 1 = 127. The largest known Mersenne prime tends to also be the largest known prime number. Currently, the largest known Mersenne prime is 257885161 − 1 and has in excess of 17 million decimal digits.[1]

Theorem. For a number of the form 2n − 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 2n − 1.

Proof. Consider the powers of 2 modulo a number of the form 2n − 1: we have \scriptstyle 1, 2, 4, 8, \ldots, 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 \scriptstyle 2^{mn} \,\equiv\, 1 \pmod {2^n - 1} \, holds and therefore the number 2mn − 1 is divisible by 2n − 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 2n − 1 has at least one divisor that is also a Mersenne number (with the exponent corresponding to that divisor of n), thus proving that 2n − 1 is also composite. But if n is prime, then 2n − 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 \scriptstyle 2^{11} - 1 \,=\, 2047 \,=\, 23 \times 89 \,=\, (2 \times 11 + 1) \times (8 \times 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 \scriptstyle M_p \, is a Mersenne prime then

2^{p-1} \cdot (2^p - 1) = \frac{M_p + 1}{2} \cdot M_p \

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

Contents

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} := \sum_{i=0}^{n-1} 1 \cdot 2^i = \frac{2^n - 1}{2 - 1} = 2^n - 1,\, n \,\ge\, 0. \,

Generating function of base 2 repunits

The ordinary generating function of base 2 repunits is

G_{\{R^{(2)}_{n}\}}(x) \equiv \sum_{n=0}^{\infty} R^{(2)}_{n} x^n = \frac{x}{(1-2x)(1-x)}. \,

Exponential generating function of base 2 repunits

The exponential generating function of base 2 repunits is

E_{\{R^{(2)}_{n-1}\}}(x) \equiv \sum_{n=1}^{\infty} R^{(2)}_{n-1} \frac{x^n}{n!} = \frac{(e^x-1)^2}{2}. \,

Sequences

A000225 \scriptstyle 2^n - 1,\, n \,\ge\, 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: \scriptstyle M_p \,=\, 2^p - 1 \,, where \scriptstyle 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 \scriptstyle M_p \,=\, 2^p - 1 \, where \scriptstyle 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 \scriptstyle p \, such that \scriptstyle M_p \,=\, 2^p - 1 \, is prime. The number of digits (base 2) in \scriptstyle M_p \,.

{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 \scriptstyle 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, ...}

See also

Notes

  1. ↑ Cooper, GIMPS, Jan. 25, 2013.

External links

Retrieved from "http://oeis.org/wiki/Mersenne_primes"
Personal tools