2
$\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$
4
  • 1
    $\begingroup$ It's fine. $2^p>10^{100000000}\implies p>1000000000\log_210\approx 332192809$ $\endgroup$
    – Hagen von Eitzen
    Apr 30, 2013 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, 2013 at 15:18
  • $\begingroup$ Count your zeroes (or nines) carefully, so that the number of them does not change when you move down your exponent. Anyway, the limits are technically those with a bunch of nines, although no Mersenne number with prime exponent manages to squeeze itself in: $$\begin{align}2^p>10^{99999999}\implies p>99999999\log_210&\approx 332192806\\ 2^p>10^{100000000}\implies p>100000000\log_210&\approx 332192809\\ 2^p>10^{999999999}\implies p>999999999\log_210&\approx 3321928092\\ 2^p>10^{1000000000}\implies p>1000000000\log_210&\approx 3321928095\end{align}$$ $\endgroup$
    – Jeppe Stig Nielsen
    Apr 3 at 12:18
  • $\begingroup$ Next time a prime exponent sneaks in, is when people want a Mersenne with 1'000'000'000'000'000'000'000'000 digits in it. The prime 3321928094887362347870317 comes in between $(10^{24}-1)\log_210$ and $10^{24}\log_210$ and should not be forgotten. $\endgroup$
    – Jeppe Stig Nielsen
    Apr 3 at 12:35

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .