```

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 + 286http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifn=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:
 #includeint 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?  ???

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.72825054586682085824In[2]:= v=N[Log[10,Sqrt[2 Pi]], 20]Out[2]= 0.39908993417905752478In[3]:= 10^(u+v)Out[3]= 13.407273846978712508

What do you get?

Code:
 #include#include#include#includeint 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

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.