mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-12-17, 05:49   #1
Unregistered
 

2·4,099 Posts
Default 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?
  Reply With Quote
Old 2006-12-17, 09:18   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-12-17, 12:53   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by akruppa View Post
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)
Mini-Geek is offline   Reply With Quote
Old 2006-12-17, 13:53   #4
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

22·7·59 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
S485122 is offline   Reply With Quote
Old 2006-12-17, 14:17   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2006-12-17, 23:07   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by Jacob Visser View Post
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
akruppa is offline   Reply With Quote
Old 2006-12-18, 06:13   #7
Unregistered
 

155078 Posts
Default Mr. Michael (Australia)

Quote:
Originally Posted by akruppa View Post
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
  Reply With Quote
Old 2006-12-18, 14:03   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-12-19, 05:50   #9
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

3×191 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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/
markr is offline   Reply With Quote
Old 2006-12-19, 14:34   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by markr View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-12-20, 01:31   #11
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Bug with particular large number VolMike YAFU 18 2012-04-09 21:39
Finding the square root of a large mersenne number Fusion_power Math 29 2010-10-14 17:05
Sieving a Large Number of k's Dougal Conjectures 'R Us 1 2010-06-17 21:48
Is this a relatively large number? MavsFan Math 3 2003-12-12 02:23

All times are UTC. The time now is 07:07.

Thu Mar 4 07:07:13 UTC 2021 up 91 days, 3:18, 1 user, load averages: 2.68, 2.52, 2.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.