mersenneforum.org > Math What size of Mersenne number ?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-29, 11:13 #1 Detheris     Feb 2020 France 2 Posts What size of Mersenne number ? Hi forum i'm noob this is my first post here my pc calculates the exponent 106 949 789 is there a method to know the size of the calculated number? (I think around 13000K)
 2020-02-29, 12:05 #2 ATH Einyen     Dec 2003 Denmark C3E16 Posts You can find the number of digits by taking the base 10 logarithm and rounding up: log10(2106949789) = 106949789* log10(2) = 106949789 * 0.301030 = 32195094.5 So the number is 32,195,095 digits long. Last fiddled with by ATH on 2020-02-29 at 12:09
 2020-02-29, 19:19 #3 Detheris     Feb 2020 France 2 Posts it's fine TY
2021-04-13, 13:46   #4
drkirkby

"David Kirkby"
Jan 2021
Althorne, Essex, UK

20910 Posts

Quote:
 Originally Posted by ATH You can find the number of digits by taking the base 10 logarithm and rounding up: log10(2106949789) = 106949789* log10(2) = 106949789 * 0.301030 = 32195094.5 So the number is 32,195,095 digits long.
Could that method be in error by one digit occasionally, as one actually wants the number of digits in 2^n -1, not those in 2^n? I would think one might run into problems with the precision of floating point arithmetic, but probably not for the exponents we are currently testing.

2021-04-13, 14:23   #5
axn

Jun 2003

3·5·331 Posts

Quote:
 Originally Posted by drkirkby Could that method be in error by one digit occasionally, as one actually wants the number of digits in 2^n -1, not those in 2^n?
No.

2021-04-13, 15:15   #6
Dr Sardonicus

Feb 2017
Nowhere

26·71 Posts

Quote:
 Originally Posted by drkirkby Could that method be in error by one digit occasionally, as one actually wants the number of digits in 2^n -1, not those in 2^n? I would think one might run into problems with the precision of floating point arithmetic, but probably not for the exponents we are currently testing.
Think: When do two consecutive integers have different numbers of decimal digits?

One thing you do have to be careful about is that the value of log(2)/log(10) is sufficienty accurate. With an exponent around 108, you want an error in the log value of significantly less than 10-8.

Now .301030 doesn't appear to be accurate enough, but looking at the more precise value 0.30102999566398 we see that .301030 is too large, but by less than 0.5 x 10-8.

2021-04-13, 15:59   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

26738 Posts

Quote:
 Originally Posted by Dr Sardonicus One thing you do have to be careful about is that the value of log(2)/log(10) is sufficienty accurate. With an exponent around 108, you want an error in the log value of significantly less than 10-8.
You need a greater precision, roughly 16 digits to get the correct answer for all p<10^8. Real example using Pari-Gp:
Code:
? n=181605302766736484827;
? \p
realprecision = 38 significant digits
?
? floor(n*log(2)/log(10)+1)
%2 = 54668643504426676183
?
? default(realprecision,100)
? \p
realprecision = 115 significant digits (100 digits displayed)
?
? floor(n*log(2)/log(10)+1)
%4 = 54668643504426676182
?
?
? n*log(2)/log(10)+1
%5 = 54668643504426676182.99999999999999999999720538018594909538656898697141084522414440557252073033365406
[For a minute forget that n is composite.]
What happened here? n has only 21 digits, but using the default precision=38 digits failed to give the number of digits in 2^n using the "known" formula, without calculating 2^n. How was it possible? The reason is that n*log(2)/log(10) was very close to an integer. [even "only" 39 digits would be enough for this example].

Another example from me in this theme: https://trac.sagemath.org/ticket/10164 .

2021-04-14, 12:50   #8
Dr Sardonicus

Feb 2017
Nowhere

107008 Posts

Quote:
 Originally Posted by R. Gerbicz You need a greater precision, roughly 16 digits to get the correct answer for all p<10^8. Real example using Pari-Gp: Code: ? n=181605302766736484827; ? \p realprecision = 38 significant digits ? ? floor(n*log(2)/log(10)+1) %2 = 54668643504426676183 ? ? default(realprecision,100) ? \p realprecision = 115 significant digits (100 digits displayed) ? ? floor(n*log(2)/log(10)+1) %4 = 54668643504426676182 ? ? ? n*log(2)/log(10)+1 %5 = 54668643504426676182.99999999999999999999720538018594909538656898697141084522414440557252073033365406 [For a minute forget that n is composite.] What happened here? n has only 21 digits, but using the default precision=38 digits failed to give the number of digits in 2^n using the "known" formula, without calculating 2^n. How was it possible? The reason is that n*log(2)/log(10) was very close to an integer. [even "only" 39 digits would be enough for this example]. Another example from me in this theme: https://trac.sagemath.org/ticket/10164 .
Since c = log(2)/log(10) is irrational, the simple continued fraction (SCF) for c does not terminate. If pn/qn is a convergent fraction,

|c - pn/qn| < 1/qnqn+1 < 1/qn^2.

So this degree of closeness is guaranteed to occur infinitely many times.

And, sure enough (I checked), 54668643504426676182/181605302766736484827 is a convergent to the SCF for c.

Are any of the convergent fractions even better approximations to c, say |c - p/q| < 1/q^3 for some q > 10, say? I don't have a clue. To get qn+1 > qn^2 the partial quotient an would have to be about as large as qn itself.

Using 10000 decimal digits precision, I had Pari-GP compute contfrac(log(2)/log(10)), which gave 9858 partial quotients, the largest of which was the 2837th of 244049. This may seem large, but it is minuscule compared to the denominator of the 2837th convergent!

2021-04-15, 06:33   #9
jnml

Feb 2012
Prague, Czech Republ

101010112 Posts

Quote:
 Originally Posted by Detheris Hi forum i'm noob this is my first post here my pc calculates the exponent 106 949 789 is there a method to know the size of the calculated number? (I think around 13000K)

"Size" is not well defined in this context. "Number of decimal" digits is, for example.

From a programmer's POV, I'd assume "size" to mean how much memory one needs
to store the number in a computer memory. Then the size is 106 949 789 bits and
that is 13 368 723.625 bytes, confirming your "around 13000K".

Last fiddled with by jnml on 2021-04-15 at 06:33

2021-04-15, 13:59   #10
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32·163 Posts

Quote:
 Originally Posted by Dr Sardonicus Since c = log(2)/log(10) is irrational, the simple continued fraction (SCF) for c does not terminate. If pn/qn is a convergent fraction, ... Are any of the convergent fractions even better approximations to c, say |c - p/q| < 1/q^3 for some q > 10, say? I don't have a clue.
Yes, c is irrational, but not algebraic, so you can't apply https://en.wikipedia.org/wiki/Roth%27s_theorem . Quite a known constant, so there could be proven theorem on good/best approx for c.

2021-04-15, 14:55   #11
Dr Sardonicus

Feb 2017
Nowhere

26·71 Posts

Quote:
 Originally Posted by R. Gerbicz Yes, c is irrational, but not algebraic, so you can't apply https://en.wikipedia.org/wiki/Roth%27s_theorem . Quite a known constant, so there could be proven theorem on good/best approx for c.
Perhaps Baker's Theorem on linear forms in logarithms gives some kind of bound on how well c can be approximated. Alas, I am not familiar enough with the result.

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil ONeil 94 2018-04-30 07:22 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 kurtulmehtap Math 12 2010-05-03 14:02 kerguilloud Math 6 2005-01-20 10:16 romanesquefr Miscellaneous Math 17 2004-12-17 12:05

All times are UTC. The time now is 03:13.

Sat May 15 03:13:35 UTC 2021 up 36 days, 21:54, 0 users, load averages: 1.83, 2.14, 2.28