# Smallest Mersenne prime with 100 million digits?

As some of you are probably aware, the Great Internet Mersenne Prime Search (GIMPS) is managing the search for the largest Mersenne primes of the form $M_p=2^p-1$, where $p$ is itself prime (GIMPS website).

The largest known prime is the 48th known Mersenne prime:

$M_{57885161} = 581887266 \ldots 724285951$ (17,425,170 digits).

This is still far from the more interesting +100 million and +1 billion digit prime numbers that exist. I came to ponder on what on what exact lower bound of prime $p$ should we be checking to arrive as such huge numbers? It was therefore back to the textbooks about logarithms.

Question: Are the following derivations correct?

Let the number of digits in $M_p$ be $n_p$. Thus we have:

$\lfloor \log_{10} M_p \rfloor = n_p - 1 \quad \text{and} \quad \lfloor \log_{2} M_p \rfloor = p - 1 \;$.

The flooring operators are removed (and $\geq$ is used instead):

$\log_{10} M_p \geq n_p - 1 \quad \text{and} \quad \log_{2} M_p \geq p - 1 \;$.

We now re-express the logarithms:

$\log_{2} M_p/\log_{2} 10 \geq n_p - 1 \quad \text{and} \quad \log_{10} M_p/\log_{10} 2 \geq p - 1 \;$.

Then we move the denominator to the right-hand side:

$\log_{2} M_p \geq (n_p - 1)\log_{2} 10 \quad \text{and} \quad \log_{10} M_p \geq (p - 1)\log_{10} 2 \;$,

and reinstate flooring operators:

$\lfloor \log_{2} M_p \rfloor = (n_p - 1)\log_{2} 10 \quad \text{and} \quad \lfloor \log_{10} M_p \rfloor = (p - 1)\log_{10} 2 \;$.

We insert the original expressions:

$p - 1 = (n_p - 1)\log_{2} 10 \quad \text{and} \quad n_p - 1 = (p - 1)\log_{10} 2 \;$,

and solve for $p$ in both expressions:

$p = 1 + (n_p - 1)\log_{2} 10 = 1 + (n_p + 1) / \log_{10} 2\;$.

Lower bounds for $p$:

For +100 million digits the lower bound for $p$ seems to be:

$p = 1 + (10^8 - 1)\log_{2} 10 \approx 3.322 \times 10^8 = 332200000 \;$,

and for +1 billion digits:

$p = 1 + (10^9 - 1)\log_{2} 10 \approx 3.322 \times 10^9 = 3322000000 \;$.

This seems to correlate with $M_{57885161}$ where $n_p = 17425170$:

$p = 1 + (17425170 - 1)\log_{2} 10 = 5.78852 \times 10^7 \gtrapprox 57885161$.

It's fine. $2^p>10^{100000000}\implies p>1000000000\log_210\approx 332192809$ – Hagen von Eitzen Apr 30 '13 at 15:15