 mersenneforum.org > Math How to compute a (large) Mersenne number
 Register FAQ Search Today's Posts Mark Forums Read  2006-12-17, 05:49 #1 Unregistered   5×1,889 Posts 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?  2006-12-17, 09:18 #2 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts 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   2006-12-17, 12:53   #3
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AC16 Posts Quote:
 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)   2006-12-17, 13:53   #4
S485122

"Jacob"
Sep 2006
Brussels, Belgium

2·13·67 Posts Quote:
 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 log10(2)is aproximatively equal to 0,30102999566398119521373889472449.

But i think the question is not the number of digits but the actual digits. To compute 232582657-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 22, 24, 28, 216, 232... until the power is the biggest one fitting in your target in the above example 22[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.   2006-12-17, 14:17 #5 dsouza123   Sep 2002 2·331 Posts 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.   2006-12-17, 23:07   #6
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts Quote:
 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   2006-12-18, 06:13   #7
Unregistered

2·32·13·41 Posts Mr. Michael (Australia)

Quote:
 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  2006-12-18, 14:03   #8
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 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.   2006-12-19, 05:50   #9
markr

"Mark"
Feb 2003
Sydney

3×191 Posts Quote:
 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/   2006-12-19, 14:34   #10
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 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.   2006-12-20, 01:31 #11 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 VolMike YAFU 18 2012-04-09 21:39 Fusion_power Math 29 2010-10-14 17:05 Dougal Conjectures 'R Us 1 2010-06-17 21:48 MavsFan Math 3 2003-12-12 02:23

All times are UTC. The time now is 11:17.

Sun Oct 17 11:17:10 UTC 2021 up 86 days, 5:46, 0 users, load averages: 1.94, 2.92, 2.95