Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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