Let M_{n} be the nth Mersenne
prime. Take a careful look at the graph of log_{2}(log_{2}(M_{n}))
versus n. (That is, the logarithm base two of the logarithm base
two of the nth Mersenne.)

One can not miss that this graph is amazingly linear. Erhardt (and
many others after him) looked at the limited data and guessed that the geometric
mean of the ratio of two successive Mersenne exponents 3/2.

Some time later Pomerance and Lenstra each
(independently) [Pomerance81,
p. 101] suggested this should be 2 raised to 1/e^{gamma} or
about 1.47576, not 3/2, where gamma is Euler's
constant gamma. This is now the accepted value, but why? Below
we will answer this question using a simple heuristic
argument. This means we try to make it seem plausible (and
eventually hope for a proof someday).

If you are in a rush, then let me simply follow Ribenboim [Ribenboim95]
and state the factor e^{gamma} comes by analogy from Mertens'
theorem. But if you have time, take a sip of coffee and join
us for a little mathematics.

Heuristic Derivation of this Mersenne Conjecture

We will argue for Lenstra and Pomerance's conjecture in the form given
in 1983 by Wagstaff [Wagstaff83] (though
we do not follow his reasoning here):

The number of Mersenne primes less than or equal to x is about
(e^{gamma}/log 2) * log log x. (Here gamma is Euler's
constant).

The expected number of Mersenne primes 2^{p}-1 with
p between x and 2x is about e^{gamma}.

The probability that 2^{p}-1 is prime is about
(e^{gamma} log ap )/(p log 2) where a=2
if p=3 (mod 4), and a=6 if p=1 (mod 4).

So how might we reach this conclusions? We will start by estimating
the probability that 2^{k}-1 is prime, and then combine
that guess with several others.

The probability that 2^{k}-1 is prime

As our first step in estimating the probability that 2^{k}-1
is prime, we recall that for 2^{k}-1 to be prime, k
must be prime (proof). Next,
by prime
number theorem the probability that a random positive integer k
is prime is (asymptotic to) 1/log(k) (where log x is the
natural logarithm). For the next step we will assume this is the
case: that k is prime.

Next, we might want to again use the prime number theorem to guess that
the probability that 2^{k}-1 is prime, is 1/log(2^{k}-1),
or about 1/(k log 2); but 2^{k}-1 does not behave
like a "random number." For example, 2^{k}-1
can only be divisible by primes of the form 2mk+1 for certain
integers
m (proof). So we
will need to adjust the estimate of probability we get from the prime
number theorem as follows.

Since 2^{k}-1 can not be even--we multiply our estimate
of the primality probability by 2 (since 2 divides 1/2 of the integers).
Similarly, unless k is 2, 2^{k}-1 can not be divisible
by 3, so we multiply our estimate of the primality probability by 3/2=1/(1-1/3)
(since 3 divides 1/3rd of the integers). In fact, for each prime
q less than 2k+1 we must multiply our estimate by q/(q-1)
= 1/(1-1/q). So we now guess that the probability that 2^{k}-1
is prime (for a given prime q) is about

"But wait" you might say, "you have log(2k), but Wagstaff says
log(ak) where a varies." Then I'd be forced to admit
I omitted something else we know about the divisors
of Mersenne numbers: they are always congruent to +/-1 modulo 8.
When k is 3 modulo 4, this means m must be 0 or 3 modulo
4, so the smallest such prime is at least 6k+1 and we must replace
the 2k in our argument above with 6k, just as Wagstaff says.
When k is 1 modulo 4, m may be 1, so we can stick with the
2k above in this case. This completes the derivation of Wagstaff's
third conclusion.

Toward a combined estimate

Let's go one step further and combine our two probability estimates:
the probability k is prime and the probability the resulting 2^{k}-1
is prime. We then get the probability that 2^{k}-1
is prime (for a random positive integer k) to be

e^{gamma}^{.} log(ak)/(k log
2 ^{.} log k)

(with a=2 or 6 as above). For large k (and indeed the
"average" integer is large), log(ak)=log a + log k
is very close (asymptotically) to just log k, so our probability
estimate simplifies to

e^{gamma}/(k log 2).

Next we will use this heuristic estimate to derive the first of Wagstaff's
three conclusions.

The number of Mersennes less than x

So, how many Mersenne primes 2^{k}-1 do we expect with 1
<k < n ? We can find this by adding the
probabilities for k=1, 2, 3, ... up to n. The easiest
way to approximate this sum would be to integrate. This gives us

approximately e^{gamma} log n / log 2
Mersenne primes 2^{k}-1 with 1 <k <
n.

Now let's rephrase this. If we wish to restrict the size of n
so that 2^{k}-1 <x, then we must stop with
n log 2 near log x, hence log n near
log log x. So we have

approximately e^{gamma} log log x / log
2 Mersenne primes less than x.

This is the first of Wagstaff's conclusions (from which the second follows
trivially).

Note: The above is definitely not the argument you find in Wagstaff's
article, but I think it is easier to follow and generalizes smoothly to
many other forms.