What size of Mersenne number ?

[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)

[ATH]

You can find the number of digits by taking the base 10 logarithm and rounding up:

log₁₀(2^106949789) = 106949789* log₁₀(2) = 106949789 * 0.301030 = 32195094.5

So the number is 32,195,095 digits long.

[Detheris]

it's fine

TY

[drkirkby]

Originally Posted by ATH

You can find the number of digits by taking the base 10 logarithm and rounding up:

log₁₀(2^106949789) = 106949789* log₁₀(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.

[axn]

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.

[Dr Sardonicus]

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 10⁸, 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.

[R. Gerbicz]

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 10⁸, 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:

? 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 .

[Dr Sardonicus]

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:

? 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 p_n/q_n is a convergent fraction,

|c - p_n/q_n| < 1/q_nq_n+1 < 1/q_n^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 q_n+1 > q_n^2 the partial quotient a_n would have to be about as large as q_n 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 2837^th of 244049. This may seem large, but it is minuscule compared to the denominator of the 2837^th convergent!

[jnml]

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".

[R. Gerbicz]

Originally Posted by Dr Sardonicus

Since c = log(2)/log(10) is irrational, the simple continued fraction (SCF) for c does not terminate. If p_n/q_n 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.

[Dr Sardonicus]

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.