mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-02-29, 11:13   #1
Detheris
 
Detheris's Avatar
 
Feb 2020
France

28 Posts
Default 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)
Detheris is offline   Reply With Quote
Old 2020-02-29, 12:05   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31·101 Posts
Default

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
ATH is offline   Reply With Quote
Old 2020-02-29, 19:19   #3
Detheris
 
Detheris's Avatar
 
Feb 2020
France

2 Posts
Default

it's fine

TY
Detheris is offline   Reply With Quote
Old 2021-04-13, 13:46   #4
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

C216 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
drkirkby is online now   Reply With Quote
Old 2021-04-13, 14:23   #5
axn
 
axn's Avatar
 
Jun 2003

2·3·827 Posts
Default

Quote:
Originally Posted by drkirkby View Post
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.
axn is offline   Reply With Quote
Old 2021-04-13, 15:15   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

453710 Posts
Default

Quote:
Originally Posted by drkirkby View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-04-13, 15:59   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5BA16 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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 .
R. Gerbicz is offline   Reply With Quote
Old 2021-04-14, 12:50   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

13×349 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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!
Dr Sardonicus is offline   Reply With Quote
Old 2021-04-15, 06:33   #9
jnml
 
Feb 2012
Prague, Czech Republ

32·19 Posts
Default

Quote:
Originally Posted by Detheris View Post
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
jnml is offline   Reply With Quote
Old 2021-04-15, 13:59   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-04-15, 14:55   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

13·349 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
2^852348659-1 is a Mersenne Number or something ONeil ONeil 94 2018-04-30 07:22
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Number of Factors for a Mersenne Number kurtulmehtap Math 12 2010-05-03 14:02
product of the n first mersenne number kerguilloud Math 6 2005-01-20 10:16
A portrait of the mersenne number romanesquefr Miscellaneous Math 17 2004-12-17 12:05

All times are UTC. The time now is 21:19.

Tue May 11 21:19:30 UTC 2021 up 33 days, 16 hrs, 0 users, load averages: 2.14, 2.41, 2.30

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.