mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-03-28, 02:10   #45
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101101000012 Posts
Default

Quote:
Originally Posted by patrik
My guess is 350 000 000 zeros.

Let p be the exponent, 30 402 457. Then the number of digits in base i is about p log 2 / log i. (Rounding to an integer towards +inf gives the exact number.)

Looking at the distribution of digits for base 10 it looks like the digits are equally likely to occur. We know that this is not true for base 2. (And if we think a bit about it we realise it is also not true for bases 4, 8, 16, 32, ....)

Assuming it were true for all bases we could estimate the number of zeros for base i to be (p log 2) / (i log i), and for all bases, (p log 2) sum_2^M(p) 1 / (i log i).

Or we could start the summing at 3 since we know our assumption is wrong for base i=2. And following Uncwilly's argument we stop the summing at base M(p) since there are no more zeros after that.

The sum can be approximated by the integral of dx / (x log x). The primitive functions are log (log x), and we get (approximate equalities):

log ( log M(p) ) - log( log 2.5 ) = log ( p log 2 ) - log ( log 2.5 ) = 16.95

After multiplying by the prefactor (p log 2) we arrive at 357 million, which I round down to 350 million since I inluded the bases 4, 8, 16 etc in the estimate.
We need to sum for base < 2^(30402457/2) because a larger base will have at most 2 digits. Does this make a significant difference to your estimation?

Last fiddled with by paulunderwood on 2006-03-28 at 02:12
paulunderwood is offline   Reply With Quote
Old 2006-03-28, 02:43   #46
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,163 Posts
Default

Quote:
After multiplying by the prefactor (p log 2) we arrive at 357 million, which I round down to 350 million since I inluded the bases 4, 8, 16 etc in the estimate.
That's a bit harsh considering there are about log_2(M43)/M43 such bases

Last fiddled with by paulunderwood on 2006-03-28 at 02:46
paulunderwood is offline   Reply With Quote
Old 2006-03-28, 06:05   #47
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

32×5×197 Posts
Default

Quote:
Originally Posted by paulunderwood
Your code is okay, except the loop for "base" should be up to 2^30402457-1 and not 30402457 .
True, oops.
Quote:
Originally Posted by paulunderwood
The loop should bail out when digits count became two
Because there are no X0 values, because that implies an even divisor?
Quote:
Originally Posted by paulunderwood
and you could have coded with "-1".
I left the number to help average things.

Quote:
Originally Posted by paulunderwood
I haven't checked "patrik"'s claim but at least your brute force method's expected number of zeroes is less than "patrik"'s mathematically computed expected number of them.
Quote:
Originally Posted by patrik
After multiplying by the prefactor (p log 2) we arrive at 357 million, which I round down to 350 million since I inluded the bases 4, 8, 16 etc in the estimate.
His, 3.5x108, is smaller than mine, 1.5x109 and as you pointed out I didn't go anywhere near high enough.

Maybe we need to go back to the drawing board.
Uncwilly is online now   Reply With Quote
Old 2006-03-28, 07:11   #48
Citrix
 
Citrix's Avatar
 
Jun 2003

62716 Posts
Default

My best estimate will be

Sigma((log2(M43)/(log2(x)*x))) for x from 2 to M43. I do not know the exact value of this? Any one know how to estimate this?

Citrix
Citrix is offline   Reply With Quote
Old 2006-03-28, 22:34   #49
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,163 Posts
Default does not end in zero

Does not end in zero...

Quote:
Originally Posted by Citrix
Can you prove this?
Firstly take any two digit representation. None apart from 10 (base M43) can end zero by considering M43==20 (base B) which is 2*B+0==M43, but M43 is prime.

Now take the three digit representations. None can end in zero becase we would have a*B^2+b*B+0==M43 (a,b<B) i.e. B (<M43) divides M43 -- a contradiction.

This can be continued for all arbritary length representation all the way to its binary form.

Whether this skews the figures in patrik's mathematical aproximation, I do not know.

On a separate note, it might also be more accurate to use a computer for small bases (ie. long strings) and to use a mathematical method for the rest.

Last fiddled with by paulunderwood on 2006-03-28 at 22:36
paulunderwood is offline   Reply With Quote
Old 2006-03-28, 22:46   #50
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,163 Posts
Default

Quote:
Originally Posted by paulunderwood
I haven't checked "patrik"'s claim but at least your brute force method's expected number of zeroes is less than "patrik"'s mathematically computed expected number of them.

Quote:
Originally Posted by patrik
After multiplying by the prefactor (p log 2) we arrive at 357 million, which I round down to 350 million since I inluded the bases 4, 8, 16 etc in the estimate.

Quote Uncwilly:
His, 3.5x108, is smaller than mine, 1.5x109 and as you pointed out I didn't go anywhere near high enough.

Maybe we need to go back to the drawing board.

\end{quotes}

Maybe! But remember your program used "log( Prime ) / log( Base )" which is wrong and grossly over estimated the number of zeroes.

Last fiddled with by paulunderwood on 2006-03-28 at 22:49
paulunderwood is offline   Reply With Quote
Old 2006-03-28, 23:24   #51
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

32·5·197 Posts
Default

Quote:
Originally Posted by paulunderwood
Does not end in zero...
.
Now take the three digit representations. None can end in zero becase we would have a*B^2+b*B+0==M43 (a,b<B) i.e. B (<M43) divides M43 -- a contradiction.
.
Whether this skews the figures in patrik's mathematical aproximation, I do not know.
And none can start with a zero, so my program needs to be adjusted to subtract 2 from every length, prior to division.

Quote:
Originally Posted by paulunderwood
On a separate note, it might also be more accurate to use a computer for small bases (ie. long strings) and to use a mathematical method for the rest.
I had started with the following formula in exsell: CEILING(30402457*LOG(2,ROW()+2)/(ROW()+2),1) in row 1
This yields 915206 for base 10, while Mike's count is 913468.
I ran this through base 65538 (max rows in exsell plus 2) and summed, yielding 52,282,506
Modifying this by subtracting 2 per base yields, 52,151,434
Since UBasic only allows for natural log, I found the conversion and applied that to the formula that I used.


Does any one have or can point to, code (or simple algorithm) to convert to different bases? I could expand the number to various bases and then count the zeros. Lest I be accused of being lazy, this is so that I can "stand on the shoulders of giants".
Uncwilly is online now   Reply With Quote
Old 2006-03-29, 00:34   #52
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default My estimate

This will print out the digits in reverse order for base b

while (n>0,print(n%b);n=floor(n/b));

=========================================

Here's my crack at the answer
x=30402457
Ln(x) = the natural log of x
p=2^x-1;
Let R(n) = floor(p^(1/n))

For z digit numbers, there are z-2 possible eligible digits to be zero.
We only need to consider bases through R(2) basically the floor(sqrt(p). Any number higher would have less than three digits and thereby not contribute a zero (the exception being where the base equals p itself)

Number
digits --- Sum the probabilites of the range:
1 * sigma( i=R(3)+1 to R(2), the value 1/i)
2 * sigma (i=R(4)+1 to R(3), the value 1/i)

..............

d * sigma(i=R(d+2)+1 to R(d+1), the value 1/i)

...............

x-2 * 1/2

Add 1 zero for base p

Sum across all number of digits, and you can rearrange the sum as

1 + sigma(i=1 to x-2, sigma(j=2,R(i), of 1/j))

simplify:
1 + sigma(i=1 to x-2, (Ln(p)/i -1))

simplify again:
(sigma(i=1 to x-2),1/i) * Ln(p)) - x -1 = 17.8072*x*Ln(2)-x-1 = 344856436

Now we have to deduct the contribution from bases b where b= 2^k (where k = 1 to x/2). That sum is sigma (k=1 to x/2 of (ceil(x/k) -2)/2^k) = 21073376
(BTW, the sum doesn't increase past the next integer after k=21)

So my estimate is roughly 324 million somewhat lower than patrik's.

Last fiddled with by grandpascorpion on 2006-03-29 at 00:37
grandpascorpion is offline   Reply With Quote
Old 2006-03-29, 06:46   #53
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

32·5·197 Posts
Default

Quote:
Originally Posted by grandpa scorpion
This will print out the digits in reverse order for base b

while (n>0,print(n%b);n=floor(n/b));
How well does that work for base 37? I think that that might work in a larger base if an array is used to store the digit characters. Although, for our case, we don't need to store the value, just check if your print statement yields a '0'. But, holding a number ~10m digits in memory and doing math on it is a bit out of the range of most simple languages.

Since, we also have the binary, could we not derive the nonadecimal (for example) expansion a bit more efficiently than a large number of divisions and mod's?
Quote:
Originally Posted by Paul Underwood
Maybe! But remember your program used "log( Prime ) / log( Base )" which is wrong and grossly over estimated the number of zeroes.
This was to convert the from natural log to logbase. The program that I was using only has natural log and not log10. Maybe I am misunderstanding, but to get the number digits in base X doesn't one need logX?
Uncwilly is online now   Reply With Quote
Old 2006-03-29, 14:20   #54
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

32×5×197 Posts
Default

Suggestion to the moderators: Create a duplicate thread in the math area starting at post 8, then delete posts 9--> in the original, and finally delete delete 54 (this post) in the duplicate.
Uncwilly is online now   Reply With Quote
Old 2006-03-30, 01:01   #55
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

66418 Posts
Default

let B^e=2^30402457

then: log(B^e)=log(2^30402457) independent of which base the log is taken

or: e*log(B)=30402457*log(2)

e (the length in base B) will be 30402457*log(2)/log(B)

because in our case "e" is a whole number, maybe I would take ceiling(30402457*log(2)/log(B))

So I think your:

Code:
 10   Prime = 30402457 : Zeros=0
 20   for Base = 3 to Prime
 30   L_g = log( Prime ) / log( Base )
 40   N_l = L_g * Prime
 50   Digits = ( N_l / Base )
 60   Zeros = Zeros + Digits
 70   next Base
 80   print Zeros
gives the wrong answer: 1,529,591,493 zeroes.

I'll have to do my own guess but others' estimates for 300M-350M zeroes in all possible whole number representations of M43 seem reasonable to me.

Last fiddled with by paulunderwood on 2006-03-30 at 01:03
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
Yes, Virginia, there _is_ a largest prime number! R.D. Silverman Data 82 2013-08-14 15:58
New largest prime number found Prime95 Miscellaneous Math 20 2008-07-29 16:58
get the 15th largest prime number in 3 months wfgarnett3 PSearch 1 2004-06-28 20:51
New largest prime number??? McBryce Lounge 39 2003-08-12 19:35

All times are UTC. The time now is 16:04.

Tue Nov 24 16:04:58 UTC 2020 up 75 days, 13:15, 4 users, load averages: 2.23, 1.83, 1.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.