Thursday, June 20, 2024

Iterated Mersenne primes

Computer scienceIterated Mersenne primes

A Mersenne number is a number of the form 2k − 1. A Mersenne prime is a Mersenne number which is also a prime.

It turns out that if 2k − 1 is prime then k must be prime, so Mersenne numbers have the form 2p − 1 is prime. What about the converse? If p is prime, is 2k − 1 also prime? No, because, for example, 211 −  1 = 1023 = 3 × 11 × 31.

If p is not just a prime but a Mersenne prime, then is 2p − 1 a prime? Sometimes, but not always. The first counterexample is p = 8191.

There is an interesting chain of iterated Mersenne primes:

This raises the question of whether m = 2M12 − 1 is prime. Direct testing using available methods is completely out of the question. The only way we’ll ever know is if there is some theoretical result that settles the question.

Here’s an easier question. Suppose m is prime. Where would it fall on the list of Mersenne primes if conjectures about the distribution of Mersenne primes are true?

This post reports

It has been conjectured that as x increases, the number of primes px such that 2p – 1 is also prime is asymptotically

eγ log x / log 2

where γ is the Euler-Mascheroni constant.

If that conjecture is true, the number of primes less than M12 that are the exponents of Mersenne primes would be approximately

eγ log M12 / log 2 = 226.2.

So if m is a Mersenne prime, it may be the 226th Mersenne prime, or Mn for some n around 226, if the conjectured distribution of Mersenne primes is correct.

We’ve discovered a dozen Mersenne primes since the turn of the century and we’re up to 51 discovered so far. We’re probably not going to get up to the 226th Mersenne prime, if there even is a 226th Mersenne prime, any time soon.


Check out our other content

Check out other tags:

Most Popular Articles