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$.
Anything questionable about this entire derivation?
This is fine. The section under Lower bounds for p is sufficient.