Marin Mersenne had a list of prime exponents p which he believed to produce primes of the form 2^{p} − 1

He got some right (the bold numbers below), he got some wrong (the crossed-out numbers), and he missed a few (the underlined numbers):

**2**, **3**, **5**, **7**, **13**, **17**, **19**, **31**, __61__, ~~67~~, __89__, __107__, **127**, ~~257~~...

Nobody knows how he came up with his list, but all the numbers he chose were at a distance of 1 or 3 from a power of two. Powers of two are 2, 4, 8, 16, 32, 64, 128, 256, ...

Meanwhile, the Wagstaff primes are of the form (2^{p} + 1) /3 for the following prime exponents p:

**3**, **5**, **7**, 11, **13**, **17**, **19**, 23, **31**, 43, **61**, 79, 101, **127**, 167, 191, 199, 313...

The values of p which also produce Mersenne primes are in bold above.

Interestingly, these numbers in bold are all also at a distance of 1 or 3 from a power of two. Most likely this is a mere coincidence involving small numbers.

Nevertheless, the “new Mersenne conjecture” posits that there may really be a link between exponents of Mersenne primes, exponents of Wagstaff primes, and primes that are near powers of two. The general idea is “never two of these without the third also”.

The exact wording of the conjecture is actually a bit stricter: primes that are either at a distance of 1 from a power of two or at a distance of 3 from a power of four.

It's generally considered trivially true. For larger p, it's extremely improbable that Mersenne primes or Wagstaff primes will ever have exponents that coincide with one another, or that either will happen to have an exponent that is anywhere near a power of two. So for p of any significant size, at most only one of the three things will ever be true at the same time. “Never two without three” is trivially true if it's always just “never two”.

The “new Mersenne conjecture” can only be *untrue* under one of the following conditions:

- The Wagstaff number with exponent 1,073,741,827 is prime
- The Wagstaff number with exponent 2,147,483,647 is prime
- Some member of an (infinite?) set of untestably large exponents produces either a Mersenne prime or Wagstaff prime, but not both.
- A new Mersenne prime is discovered (with exponent not in the untestably large set mentioned above), and the Wagstaff number with the same exponent
*is also prime*

It is extremely unlikely that any of the above are true, and therefore the conjecture itself is almost certainly trivially true.

The exponents in the untestably large set are {
2^{61}−1,
2^{84}+3,
2^{89}−1,
2^{94}−3,
2^{107}−1,
2^{116}−3,
2^{122}−3,
2^{127}−1, ... }, and consist of the members of sequence OEIS A122834) which have not been ruled out or mentioned earlier. The smallest exponent is 2^{61}−1 = 2305843009213693951 ≈ 2.3 quintillion. With current computers it is not possible to do a primality test or probable-prime test for exponents larger than about one billion, although it is possible to search for factors.

The probability that 2^{p}−1 is prime for a specific *p* is asymptotically proportional to log *p* / *p*, which rapidly declines for increasing *p*. Since the untestably large set is very sparse and very rapidly increasing, *a priori* it seems extremely unlikely that it could ever produce any primes.

There are 51 known exponents of Mersenne primes. If we ignore the ones less than or equal to 127 and use the rest as exponents of Wagstaff numbers, then all of these Wagstaff numbers have known factors except the following, which have been proven composite by PRP test:

exponent | Type-5 PRP-3 residue | Type-1 PRP-3 residue |
---|---|---|

19 937 | C82DBE5680C95005 | CAF7FC34947CB1FE |

30 402 457 | 6091218A6A170737 | AA5C02C10B16CD58 |

74 207 281 | 500EBDEDCC71D74A | 699611E370B45F4A |

82 589 933 | 891318A6346D7DE3 | 9841E7C75AC01D0C |

There are 43 known exponents of Wagstaff primes. If we ignore the ones less than or equal to 127 and use the rest as exponents of Mersenne numbers, then all of these Mersenne numbers have known factors except the following, which have been proven composite by Lucas-Lehmer test:

exponent | Lucas-Lehmer residue |
---|---|

117 239 | A7C9C26B0E3D749D |

374 321 | 085D57AAC25F1241 |

986 191 | 9928ABEFD2E39BD7 |

No known exponents above 127 of Mersenne primes are particularly close to powers of two. The nearest misses are: 521 (“close” to 512) and 132049 (“close” to 131072).

Similarly, no known exponents above 127 of Wagstaff primes are particularly close to powers of two. The nearest miss is 267107 (“close” to 262144).

The primes p above 127 that are at a distance of 1 from a power of two or at a distance of 3 from a power of four are (OEIS sequence A122834):

exponent | Mersenne number factored? or Lucas-Lehmer residue or PRP-3 residue | Wagstaff number factored? or Type-5 PRP-3 residue | Notes |
---|---|---|---|

257 | Factored | Factored | MF4 |

1 021 | Factored | Factored | |

4 093 | Factored | Factored | |

4 099 | Factored | Factored | |

8 191 | Factored | D994CA9C6CF44A79 | MM13 |

16 381 | 025005C687C28BD3 (LL) | Factored | |

65 537 | Factored | Factored | MF5 |

65 539 | Factored | Factored | |

131 071 | Factored | Factored | MM17 |

262 147 | Factored | Factored | |

524 287 | Factored | 3861C6702EB98275 | MM19 |

1 048 573 | Factored | A8DC06A8467759B3 | |

4 194 301 | Factored | Factored | |

16 777 213 | AF44FAB38FEC83A4 (LL) | Factored | |

268 435 459 | EB4264A6767705** (PRP-3) | Factored |

Beyond this point, the exponents of this sequence become too big to perform Lucas-Lehmer tests or PRP tests, as it becomes increasingly improbable to find a prime number within a very short distance of a power of two. After all, Mersenne primes and Fermat primes themselves are a subset of such numbers, and they are very rare.

exponent | Mersenne number factored? | Wagstaff number factored? | Notes |
---|---|---|---|

1 073 741 827 | Factored | no factor < 2^{84} | |

2 147 483 647 | Factored | no factor < 2^{86} | MM31 |

2 305 843 009 213 693 951 | MM61 | ||

19 342 813 113 834 066 795 298 819 | |||

618 970 019 642 690 137 449 562 111 | MM89 | ||

etc. |

The second, third and fifth exponents above are the Mersenne primes 2^{31} − 1 and 2^{61} − 1 and 2^{89} − 1

Mersenne numbers with exponents that are Mersenne primes are known as double Mersennes.

Mersenneplustwo Factorizations, finding factors of Wagstaff numbers with exponents that are exponents of Mersenne primes

Double Mersennes Prime Search: Found Factors