The “new Mersenne conjecture”

Marin Mersenne had a list of prime exponents p which he believed to produce primes of the form 2p − 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 (2p + 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”.

Current status

Summary

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

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 { 261−1, 284+3, 289−1, 294−3, 2107−1, 2116−3, 2122−3, 2127−1, ... }, and consist of the members of sequence OEIS A122834) which have not been ruled out or mentioned earlier. The smallest exponent is 261−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 2p−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.

Details

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:

exponentType-5
PRP-3 residue
Type-1
PRP-3 residue
19 937C82DBE5680C95005CAF7FC34947CB1FE
30 402 4576091218A6A170737AA5C02C10B16CD58
74 207 281500EBDEDCC71D74A699611E370B45F4A
82 589 933891318A6346D7DE39841E7C75AC01D0C

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:

exponentLucas-Lehmer
residue
117 239A7C9C26B0E3D749D
374 321085D57AAC25F1241
986 1919928ABEFD2E39BD7

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):

exponentMersenne number factored?
or Lucas-Lehmer residue
or PRP-3 residue
Wagstaff number factored?
or Type-5 PRP-3 residue
Notes
257FactoredFactoredMF4
1 021FactoredFactored
4 093FactoredFactored
4 099FactoredFactored
8 191FactoredD994CA9C6CF44A79MM13
16 381025005C687C28BD3 (LL)Factored
65 537FactoredFactoredMF5
65 539FactoredFactored
131 071FactoredFactoredMM17
262 147FactoredFactored
524 287Factored3861C6702EB98275MM19
1 048 573FactoredA8DC06A8467759B3
4 194 301FactoredFactored
16 777 213AF44FAB38FEC83A4 (LL)Factored
268 435 459EB4264A6767705** (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.

exponentMersenne number factored?Wagstaff number factored?Notes
1 073 741 827Factoredno factor < 284
2 147 483 647Factoredno factor < 286MM31
2 305 843 009 213 693 951MM61
19 342 813 113 834 066 795 298 819
618 970 019 642 690 137 449 562 111MM89
etc.

The second, third and fifth exponents above are the Mersenne primes 231 − 1 and 261 − 1 and 289 − 1

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

Links

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

Double Mersennes Prime Search: Found Factors


Home page