1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It's fine. $2^p>10^{100000000}\implies p>1000000000\log_210\approx 332192809$ $\endgroup$ – Hagen von Eitzen Apr 30 '13 at 15:15
  • $\begingroup$ (+1) for simplicity. I have always had a tendency to ever-engineer things. Anyway ... it was fun. $\endgroup$ – Ole Thomsen Buus Apr 30 '13 at 15:18
0
$\begingroup$

This is fine. The section under Lower bounds for p is sufficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.