How to compute a (large) Mersenne number

If could you please advise me how do the mathematicians workout the exact digits of a large Mersen prime?

[akruppa]

The number of digits in the base-b representation of a positive integer n is floor(log_[I]b[/I](n))+1. If we set n=2^[I]p[/I]-1, we get floor(log_[I]b[/I](2^[I]p[/I]-1))+1 = floor(p*log_[I]b[/I](2))+1. This equaliy is exact for p>0, because 2^[I]p[/I] never ends in 0, so subtracting 1 can't change the number of digits.

Alex

[Mini-Geek]

Originally Posted by akruppa

The number of digits in the base-b representation of a positive integer n is floor(log_[I]b[/I](n))+1. If we set n=2^[I]p[/I]-1, we get floor(log_[I]b[/I](2^[I]p[/I]-1))+1 = floor(p*log_[I]b[/I](2))+1. This equaliy is exact for p>0, because 2^[I]p[/I] never ends in 0, so subtracting 1 can't change the number of digits.

Alex

As I just found out by looking at the source of the Bencharks page on the GIMPS site, for Mersenne numbers in base 10 there is an easier way: the floor of the exponent times 0.301029995664 plus one (or: floor(p*0.301029995664+1) where p is the p in 2^p-1)

[S485122]

Originally Posted by Mini-Geek

As I just found out by looking at the source of the Bencharks page on the GIMPS site, for Mersenne numbers in base 10 there is an easier way: the floor of the exponent times 0.301029995664 plus one (or: floor(p*0.301029995664+1) where p is the p in 2^p-1)

That is because log₁₀(2)is aproximatively equal to 0,30102999566398119521373889472449.

But i think the question is not the number of digits but the actual digits. To compute 2^32582657-1 one can use programs that will compute almost any expression like "Mathematica" or with a little courage compute it by "hand" or aided by a calculator... Obviously the number exceeds the number of digits a calculator can hold, so one has to compute the number in chunks a little big smaller than the maximum your calculator can hold (f.i. if your calculator holds ten digits you would calculate in chunks of 8 or 7 to be safe digits.)

For instance start by computing powers of powers of two 2², 2⁴, 2⁸, 2¹⁶, 2³²... until the power is the biggest one fitting in your target in the above example 2^2[sup]24[/sup], then add the next biggest exponent you computed and go on like this until you have your number. Then substract 1.

You can also write a little program to execute large multiplications.

Anyway since you want to have an exact result you can not use shortcuts (like logs or "simple" calcualtors) because you would not have enough precision.

[dsouza123]

In base 2 it is simple to get the binary digits of a Mersenne prime.

For example 2^13 - 1 = 8192 - 1 = 8191 in base 10

but in base 2 it is 10000000000000 - 1 = 1111111111111 base 2
or simply 13 ones for the case of 2^13 - 1.

In base 2 it is the number made by the sequence of p ones,
with p the prime exponent in the formula 2^p - 1.

[akruppa]

Originally Posted by Jacob Visser

But i think the question is not the number of digits but the actual digits.

Ah, you may be right. I instantly thought "number of digits" as that is such a frequent question.

Alex

Originally Posted by akruppa

Ah, you may be right. I instantly thought "number of digits" as that is such a frequent question.

Alex

Thank you u all for your time and your contribution. That's right as said by Jacob Visser, my question is How do you work out the actual digits of Mersen prime? How do you compute 2^32582657-1 = ...??

Do you know any resource or program that I could use?

Thank you.
Michael

[R.D. Silverman]

Originally Posted by Unregistered

Thank you u all for your time and your contribution. That's right as said by Jacob Visser, my question is How do you work out the actual digits of Mersen prime? How do you compute 2^32582657-1 = ...??

Do you know any resource or program that I could use?

Thank you.
Michael

One writes a computer program that can do multiple precision arithmetic.

Ask yourself: "How does one compute 2^19 - 1 in decimal"?, for example.

Look up the "binary method for exponentiation". I give an example here.

19 = 10011 in binary. Strike out the leading 1. This gives 0011.
Starting with x = 2, and moving from left to right, everytime we see
a 0, we square x. Everytime we see a 1, we square then multiply by 2.
Thus:

2
2^2 = 4
4^2 = 16
16^2 * 2 = 512
512^2 * 2 = 524288

Now just subtract 1.

Thus, to compute 2^p requires ceiling(log p) squarings, plus a multiplication
by 2 for each bit that is lit in the binary representation of p.

[markr]

Originally Posted by Unregistered

Do you know any resource or program that I could use?

A similar question was asked in this thread http://www.mersenneforum.org/showthread.php?t=5493 and one answer was to use a program called mprint, which can be found at http://www.apfloat.org/apfloat/

[R.D. Silverman]

Originally Posted by markr

A similar question was asked in this thread http://www.mersenneforum.org/showthread.php?t=5493 and one answer was to use a program called mprint, which can be found at http://www.apfloat.org/apfloat/

Writing a suboutine that does multi-precision multiplication is not
that difficult. The O.P. might actually learn something if he coded
it himself. Coding binary exponentiation is fairly straightforward as well.

[akruppa]

But the OP asked for "large Mersen [sic] prime," which probably means multi-million digit numbers. Quadratic time algorithms won't cut it here, and subquadratic base conversion is a bit of work.

Writing multi-precision code is certainly a good programming exercise, but I think this particular task is too hard as a starting point.

Alex