Mersenne prime
That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century.
Mersenne primes were studied in antiquity because of their close connection to perfect numbers: the Euclid–Euler theorem asserts a one-to-one correspondence between even perfect numbers and Mersenne primes.
In December 2020, a major milestone in the project was passed after all exponents below 100 million were checked at least once.
The Lenstra–Pomerance–Wagstaff conjecture claims that there are infinitely many Mersenne primes and predicts their order of growth and frequency: For every number n, there should on average be about
To find a primitive polynomial of Mersenne number order requires knowing the factorization of that number, so Mersenne primes allow one to find primitive polynomials of very high order.
Mersenne primes Mp are closely connected to perfect numbers.
In the 4th century BC, Euclid proved that if 2p − 1 is prime, then 2p − 1(2p − 1) is a perfect number.
In the 18th century, Leonhard Euler proved that, conversely, all even perfect numbers have this form.
His next entry, 31, was correct, but the list then became largely incorrect, as Mersenne mistakenly included M67 and M257 (which are composite) and omitted M61, M89, and M107 (which are prime).
Lucas had shown another error in Mersenne's list in 1876 by demonstrating that M67 was composite without finding a factor.
[8] Without speaking a word, he went to a blackboard and raised 2 to the 67th power, then subtracted one, resulting in the number 147,573,952,589,676,412,927.
On the other side of the board, he multiplied 193,707,721 × 761,838,257,287 and got the same number, then returned to his seat (to applause) without speaking.
The next (in historical, not numerical order) was M127, found by Édouard Lucas in 1876, then M61 by Ivan Mikheevich Pervushin in 1883.
A notable contribution was made by retired Yale physics professor Horace Scudder Uhler, who did the calculations for exponents 157, 167, 193, 199, 227, and 229.
The search for Mersenne primes was revolutionized by the introduction of the electronic digital computer.
Alan Turing searched for them on the Manchester Mark 1 in 1949,[12] but the first successful identification of a Mersenne prime, M521, by this means was achieved at 10:00 pm on January 30, 1952, using the U.S. National Bureau of Standards Western Automatic Computer (SWAC) at the Institute for Numerical Analysis at the University of California, Los Angeles (UCLA), under the direction of D. H. Lehmer, with a computer search program written and run by Prof. R. M. Robinson.
It was the first Mersenne prime to be identified in thirty-eight years; the next one, M607, was found by the computer a little less than two hours later.
In general, the number of digits in the decimal representation of Mn equals ⌊n × log102⌋ + 1, where ⌊x⌋ denotes the floor function (or equivalently ⌊log10Mn⌋ + 1).
In September 2008, mathematicians at UCLA participating in the Great Internet Mersenne Prime Search (GIMPS) won part of a $100,000 prize from the Electronic Frontier Foundation for their discovery of a very nearly 13-million-digit Mersenne prime.
The prize, finally confirmed in October 2009, is for the first known prime with at least 10 million digits.
[13] On April 12, 2009, a GIMPS server log reported that a 47th Mersenne prime had possibly been found.
On January 25, 2013, Curtis Cooper, a mathematician at the University of Central Missouri, discovered a 48th Mersenne prime, 257,885,161 − 1 (a number with 17,425,170 digits), as a result of a search executed by a GIMPS server network.
[14] On January 19, 2016, Cooper published his discovery of a 49th Mersenne prime, 274,207,281 − 1 (a number with 22,338,618 digits), as a result of a search executed by a GIMPS server network.
[15][16][17] This was the fourth Mersenne prime discovered by Cooper and his team in the past ten years.
[18] On January 3, 2018, it was announced that Jonathan Pace, a 51-year-old electrical engineer living in Germantown, Tennessee, had found a 50th Mersenne prime, 277,232,917 − 1 (a number with 23,249,425 digits), as a result of a search executed by a GIMPS server network.
A computer volunteered by Patrick Laroche from Ocala, Florida made the find on December 7, 2018.
[22] In late 2020, GIMPS began using a new technique to rule out potential Mersenne primes called the Probable prime (PRP) test, based on development from Robert Gerbicz in 2017, and a simple way to verify tests developed by Krzysztof Pietrzak in 2018.
[23] On October 12, 2024, a user named Luke Durant from San Jose, California, found the current largest known Mersenne prime, 2136,279,841 − 1, having 41,024,320 digits.
[31] The table below shows factorizations for the first 20 composite Mersenne numbers (sequence A244453 in the OEIS).
The only known Mersenne–Fermat primes with r > 1 are In fact, MF(p, r) = Φpr(2), where Φ is the cyclotomic polynomial.
