20061217, 05:49  #1 
2·4,099 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?

20061217, 09:18  #2 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
The number of digits in the baseb 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 
20061217, 12:53  #3  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:


20061217, 13:53  #4  
Sep 2006
Brussels, Belgium
2^{2}·7·59 Posts 
Quote:
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^{4}, 2^{8}, 2^{16}, 2^{32}... 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. 

20061217, 14:17  #5 
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. 
20061217, 23:07  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 

20061218, 06:13  #7  
15507_{8} Posts 
Mr. Michael (Australia)
Quote:
Do you know any resource or program that I could use? Thank you. Michael 

20061218, 14:03  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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. 

20061219, 05:50  #9 
"Mark"
Feb 2003
Sydney
3×191 Posts 
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/

20061219, 14:34  #10  
Nov 2003
16444_{8} Posts 
Quote:
Writing a suboutine that does multiprecision 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. 

20061220, 01:31  #11 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
But the OP asked for "large Mersen [sic] prime," which probably means multimillion digit numbers. Quadratic time algorithms won't cut it here, and subquadratic base conversion is a bit of work.
Writing multiprecision code is certainly a good programming exercise, but I think this particular task is too hard as a starting point. Alex 
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  20121109 21:16 
Bug with particular large number  VolMike  YAFU  18  20120409 21:39 
Finding the square root of a large mersenne number  Fusion_power  Math  29  20101014 17:05 
Sieving a Large Number of k's  Dougal  Conjectures 'R Us  1  20100617 21:48 
Is this a relatively large number?  MavsFan  Math  3  20031212 02:23 