wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> A Beastly Number
        
(Message started by: ThudanBlunder on Nov 26th, 2008, 9:05am)
Title: A Beastly Number
Post by ThudanBlunder on Nov 26th, 2008, 9:05am
a) Find the first 6 digits of (10666)!

b) How many trailing zeros does the above number have?
Title: Re: A Beastly Number
Post by Barukh on Dec 2nd, 2008, 10:32am
For an easier part b), I get: [hide]2664(5667 - 1)[/hide]
Title: Re: A Beastly Number
Post by Barukh on Dec 3rd, 2008, 12:31am
According to the following article (http://www.pims.math.ca/pi/issue7/page10-12.pdf), solving part a) may require calculation of a certain logarithm to a precision of more than 670 decimal digits!

:o
Title: Re: A Beastly Number
Post by ThudanBlunder on Dec 4th, 2008, 6:56pm

on 12/02/08 at 10:32:03, Barukh wrote:
For an easier part b), I get: [hide]2664(5667 - 1)[/hide]

If we take n/4 as an estimate for the number of trailing zeros, we get 2.5*10665
Your number is 5 times this.  
Title: Re: A Beastly Number
Post by Barukh on Dec 5th, 2008, 12:15pm

on 12/04/08 at 18:56:10, ThudanBlunder wrote:
Your number is 5 times this.  

Yes, I should've written 5666 instead. But now I realized the answer is incorrect anyway (doesn't take into account fractions).

To write the answer in a "compact form" may be as difficult as part a) then...
Title: Re: A Beastly Number
Post by SMQ on Dec 5th, 2008, 12:32pm
      http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subinfty.gif
2)  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif10666/5nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif
     n=1
Where in practice the upper bound can be reduced to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif666 log 10 / log 5http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif = 952
 
Edit:
 		  
= 2666http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif5666 / 4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif +
 		  
286
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif
n=1
  		 
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif2666/5nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif
 
Edit2: all of which I think I can safely assume anyone hanging around in Putnam already knew (and is clearly the driver for Barukh's answer), but since this thread has only seen a little action I thought I'd put it out there anyway. ;)

--SMQ
Title: Re: A Beastly Number
Post by Barukh on Dec 6th, 2008, 9:52am
SMQ, you are right. My answer is wrong, since it doesn't take into account the second term in your formula - the sum which is challenging to evaluate.

After working it out, I get the following answer to b): 26645666 - 143.  ::)

I will supply details later, after I find the answer to the first question.
Title: Re: A Beastly Number
Post by Eigenray on Dec 6th, 2008, 12:25pm

on 12/06/08 at 09:52:06, Barukh wrote:
After working it out, I get the following answer to b): 26645666 - 143.  ::)

So is there a clever way to compute [hide]the sum of the digits of 2666 = 34004...233245[/hide]?

Actually, the approximation [hide]333*log5(2)[/hide] is pretty good here.
Title: Re: A Beastly Number
Post by Barukh on Dec 7th, 2008, 6:27am

on 12/06/08 at 12:25:31, Eigenray wrote:
So is there a clever way to compute [hide]the sum of the digits of 2666 = 34004...233245[/hide]?

I don't know. I used high-precision software (MPFR) to compute the number (I still want to get a confirmation it's correct).


Quote:
Actually, the approximation [hide]333*log5(2)[/hide] is pretty good here.

Yes, but it may be quite inaccurate for other exponents. In the attached graph, I plotted the discrepancies between your approximation and actual number for all cases 10n with 10 < n < 2000.

Again, if my calculations are correct.
Title: Re: A Beastly Number
Post by Barukh on Dec 7th, 2008, 11:21pm
I get the following answer to part a):

13407273847...
Title: Re: A Beastly Number
Post by Eigenray on Dec 8th, 2008, 7:57am

on 12/07/08 at 23:21:10, Barukh wrote:
I get the following answer to part a):

13407273847...

Are you sure it's not 134072738469787?  But the first 6 digits are correct :)

And the 143 is correct, as the following short (but rather inefficient) program shows:

Code:
#include<stdio.h>
int A[300];
int main() {
 int n,i,c;
 A[0]=1;
 for(n=0;n<666;n++) for(c=i=0;i<300;i++) {
   c+=2*A[i];
   A[i]=c%5;
   c/=5;
 }
 for(c=i=0;i<300;i++) c+=A[i];
 printf("%i\n",c/4);
}
Title: Re: A Beastly Number
Post by Barukh on Dec 8th, 2008, 10:19am

on 12/08/08 at 07:57:32, Eigenray wrote:
Are you sure it's not 134072738469787?  

Hmm... I did calculate the logarithm with very high precision, so at least 15 digits should be accurate. Then, I did exponentiation with a double precision. Could it be I lost 5 digits of accuracy there?  ???

What's your method?
Title: Re: A Beastly Number
Post by Eigenray on Dec 8th, 2008, 12:44pm

Code:
In[1]:= u=1-FractionalPart[ N[10^666 Log[10,E], 686] ]
Out[1]= 0.72825054586682085824
In[2]:= v=N[Log[10,Sqrt[2 Pi]], 20]
Out[2]= 0.39908993417905752478
In[3]:= 10^(u+v)
Out[3]= 13.407273846978712508

What do you get?

Edit: And here it is with [link=http://www.mpfr.org/]MPFR[/link]:

Code:
#include<stdlib.h>
#include<stdio.h>
#include<gmp.h>
#include<mpfr.h>

int main() {
 mpfr_t u,v;
 mpfr_set_default_prec(10000);

 mpfr_init_set_ui(v,10,GMP_RNDN);
 mpfr_pow_ui(v,v,666,GMP_RNDN); //v=10^666

 mpfr_init_set_ui(u,1,GMP_RNDN);
 mpfr_exp(u,u,GMP_RNDN);
 mpfr_log10(u,u,GMP_RNDN);  //u=log_10 e
 mpfr_mul(u,u,v,GMP_RNDN);
 mpfr_frac(u,u,GMP_RNDN);  //u=frac[10^666 log_10 e]
 
 mpfr_set_si(v,-1,GMP_RNDN);
 mpfr_acos(v,v,GMP_RNDN);
 mpfr_mul_ui(v,v,2,GMP_RNDN);  //v=2pi
 mpfr_log10(v,v,GMP_RNDN);
 mpfr_div_ui(v,v,2,GMP_RNDN);  //v=log(sqrt(2pi))

 mpfr_sub(v,v,u,GMP_RNDN);
 mpfr_ui_pow(v,10,v,GMP_RNDN);  //10^(v-u)
 mpfr_out_str(stdout,10,20,v,GMP_RNDN);
 printf("\n");
}

Gives 1.3407273846978712508

(I already had GMP but apparently it doesn't do logs.  So I downloaded the MPFR sources and started ./configure; make.  Then I realized I could install it through Cygwin, and wrote the above before it finished compiling.)
Title: Re: A Beastly Number
Post by ThudanBlunder on Dec 9th, 2008, 4:03pm
My source (http://books.google.co.uk/books?id=52N0JJBspM0C&pg=PA350&dq=leviathan+1735+n!&ei=zAc_SdD1AqaGzgTPnbnADg)for this problem got yet a different answer, 1.340727397...
Title: Re: A Beastly Number
Post by Eigenray on Dec 9th, 2008, 5:32pm
The funny thing is that he did compute the fractional part of 10666/log(10) correctly to 14 digits.  But he decided to round it to 8 digits before exponentiating, and then claim 10 digits of accuracy in the result:

Quote:
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif} x 10-0.27174945 = 1.340727397,

which is silly.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board