Mersenne conjectures: Difference between revisions
No edit summary Tags: Manual revert Reverted |
Tag: Reverted |
||
Line 146: | Line 146: | ||
Renaud Lifchitz has shown that the ''NMC'' is true for all integers less than or equal to 32582656<ref>[http://primes.utm.edu/mersenne/NewMersenneConjecture.html The New Mersenne Prime Conjecture on Prime Pages]</ref> by systematically testing all primes for which it is already known that one of the conditions holds. [http://www.primenumbers.net/rl/nmc/ His website] documents the verification of results up to this number. Another, currently more up-to-date status page on the NMC is [http://primes.utm.edu/mersenne/NewMersenneConjecture.html The New Mersenne Prime conjecture.] |
Renaud Lifchitz has shown that the ''NMC'' is true for all integers less than or equal to 32582656<ref>[http://primes.utm.edu/mersenne/NewMersenneConjecture.html The New Mersenne Prime Conjecture on Prime Pages]</ref> by systematically testing all primes for which it is already known that one of the conditions holds. [http://www.primenumbers.net/rl/nmc/ His website] documents the verification of results up to this number. Another, currently more up-to-date status page on the NMC is [http://primes.utm.edu/mersenne/NewMersenneConjecture.html The New Mersenne Prime conjecture.] |
||
The New Mersenne Conjecture implies that the [[Catalan–Mersenne number conjecture]] is false, since (2<sup>2<sup>127</sup>−1</sup>+1)/3 is divisible by 886407410000361345663448535540258622490179142922169401, hence composite. |
The New Mersenne Conjecture implies that the [[Catalan–Mersenne number conjecture]] is false, since (2<sup>2<sup>127</sup>−1</sup>+1)/3 is divisible by 886407410000361345663448535540258622490179142922169401, hence composite.<ref>[https://www.mersenneforum.org/showthread.php?t=25703 MersenneForm]</ref> |
||
== Lenstra–Pomerance–Wagstaff conjecture == |
== Lenstra–Pomerance–Wagstaff conjecture == |
Revision as of 09:17, 25 January 2021
In mathematics, the Mersenne conjectures concern the characterization of prime numbers of a form called Mersenne primes, meaning prime numbers that are a power of two minus one.
Original Mersenne conjecture
The original, called Mersenne's conjecture, was a statement by Marin Mersenne in his Cogitata Physico-Mathematica (1644; see e.g. Dickson 1919) that the numbers were prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and were composite for all other positive integers n ≤ 257. Due to the size of these numbers, Mersenne did not and could not test all of them, nor could his peers in the 17th century. It was eventually determined, after three centuries and the availability of new techniques such as the Lucas–Lehmer test, that Mersenne's conjecture contained five errors, namely two are composite (those corresponding to the primes n = 67, 257) and three omitted primes (those corresponding to the primes n = 61, 89, 107). The correct list is: n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.
While Mersenne's original conjecture is false, it may have led to the New Mersenne conjecture.
New Mersenne conjecture
The New Mersenne conjecture or Bateman, Selfridge and Wagstaff conjecture (Bateman et al. 1989) states that for any odd natural number p, if any two of the following conditions hold, then so does the third:
- p = 2k ± 1 or p = 4k ± 3 for some natural number k. (OEIS: A122834)
- 2p − 1 is prime (a Mersenne prime). (OEIS: A000043)
- (2p + 1) / 3 is prime (a Wagstaff prime). (OEIS: A000978)
If p is an odd composite number, then 2p − 1 and (2p + 1)/3 are both composite. Therefore it is only necessary to test primes to verify the truth of the conjecture.
Currently, the known numbers for which all three conditions hold are: 3, 5, 7, 13, 17, 19, 31, 61, 127 (sequence A107360 in the OEIS). It is also a conjecture that no number which is greater than 127 satisfies all three conditions. As of February 2020 all the Mersenne primes up to 243112609−1 are known, and for none of these does the third condition hold except for the ones just mentioned.[1]
Primes which satisfy at least one condition are
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 67, 79, 89, 101, 107, 127, 167, 191, 199, 257, 313, 347, 521, 607, 701, 1021, 1279, 1709, 2203, 2281, 2617, 3217, 3539, 4093, 4099, 4253, 4423, 5807, 8191, 9689, 9941, ... (sequence A120334 in the OEIS)
Note that the two primes for which the original Mersenne conjecture is false (67 and 257) satisfy the first condition of the new conjecture (67=26+3, 257=28+1), but not the other two. 89 and 107, which were missed by Mersenne, satisfy the second condition but not the other two. Mersenne may have thought that 2p − 1 is prime only if p = 2k ± 1 or p = 4k ± 3 for some natural number k, but if he thought it was "if and only if" he would have included 61.
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 |
---|---|---|---|---|---|---|---|---|---|
31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 |
73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 | 113 |
127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 | 229 |
233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 |
353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 |
419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 | 463 |
467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 | 541 |
Red: p is of the form 2n±1 or 4n±3 | Cyan background: 2p-1 is prime | Italics: (2p+1)/3 is prime | Bold: p satisfies at least one condition |
The New Mersenne conjecture can be thought of as an attempt to salvage the centuries-old Mersenne's conjecture, which is false. However, according to Robert D. Silverman, John Selfridge agreed that the New Mersenne conjecture is "obviously true" as it was chosen to fit the known data and counter-examples beyond those cases are exceedingly unlikely. It may be regarded more as a curious observation than as an open question in need of proving.
Renaud Lifchitz has shown that the NMC is true for all integers less than or equal to 32582656[2] by systematically testing all primes for which it is already known that one of the conditions holds. His website documents the verification of results up to this number. Another, currently more up-to-date status page on the NMC is The New Mersenne Prime conjecture.
The New Mersenne Conjecture implies that the Catalan–Mersenne number conjecture is false, since (22127−1+1)/3 is divisible by 886407410000361345663448535540258622490179142922169401, hence composite.[3]
Lenstra–Pomerance–Wagstaff conjecture
Lenstra, Pomerance, and Wagstaff have conjectured that there is an infinite number of Mersenne primes, and, more precisely, that the number of Mersenne primes less than x is asymptotically approximated by
where γ is the Euler–Mascheroni constant. In other words, the number of Mersenne primes with exponent p less than y is asymptotically
This means that there should on average be about ≈ 5.92 primes p of a given number of decimal digits such that is prime. The conjecture is fairly accurate for the first 40 Mersenne primes, but between 220,000,000 and 285,000,000 there are at least 12,[5] rather than the expected number which is around 3.7.
More generally, the number of primes p ≤ y such that is prime (where a, b are coprime integers, a > 1, −a < b < a, a and b are not both perfect r-th powers for any natural number r > 1, and −4ab is not a perfect fourth power) is asymptotically
where m is the largest nonnegative integer such that a and −b are both perfect 2m-th powers. The case of Mersenne primes is one case of (a, b) = (2, 1).
See also
- Gillies' conjecture on the distribution of numbers of prime factors of Mersenne numbers
- Lucas–Lehmer primality test
- Lucas primality test
- Catalan's Mersenne conjecture
- Mersenne's laws
References
- Bateman, P. T.; Selfridge, J. L.; Wagstaff Jr., Samuel S. (1989). "The new Mersenne conjecture". American Mathematical Monthly. 96 (2). Mathematical Association of America: 125–128. doi:10.2307/2323195. JSTOR 2323195. MR 0992073.
- Dickson, L. E. (1919). History of the Theory of Numbers. Carnegie Institute of Washington. p. 31. OL 6616242M. Reprinted by Chelsea Publishing, New York, 1971, ISBN 0-8284-0086-5.
- ^ James Wanless. "Mersenneplustwo Factorizations".
- ^ The New Mersenne Prime Conjecture on Prime Pages
- ^ MersenneForm
- ^ a b Heuristics: Deriving the Wagstaff Mersenne Conjecture. The Prime Pages. Retrieved on 2014-05-11.
- ^ Michael Le Page (Aug 10, 2019). "Inside the race to find the first billion-digit prime number". New Scientist.
External links
- The Prime Glossary. New Mersenne prime conjecture.