wu :: forums « wu :: forums - A Beastly Number » Welcome, Guest. Please Login or Register. Aug 12th, 2022, 8:07am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: SMQ, Icarus, william wu, Grimbal, towr, Eigenray)    A Beastly Number « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: A Beastly Number  (Read 1798 times)
ThudnBlunder
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 A Beastly Number   « on: Nov 26th, 2008, 9:05am » Quote Modify

a) Find the first 6 digits of (10666)!

b) How many trailing zeros does the above number have?
 « Last Edit: Nov 26th, 2008, 1:12pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   « Reply #1 on: Dec 2nd, 2008, 10:32am » Quote Modify

For an easier part b), I get: 2664(5667 - 1)
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   « Reply #2 on: Dec 3rd, 2008, 12:31am » Quote Modify

According to the following article, solving part a) may require calculation of a certain logarithm to a precision of more than 670 decimal digits!

 IP Logged
ThudnBlunder
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: A Beastly Number   « Reply #3 on: Dec 4th, 2008, 6:56pm » Quote Modify

on Dec 2nd, 2008, 10:32am, Barukh wrote:
 For an easier part b), I get: 2664(5667 - 1)

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.
 IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   « Reply #4 on: Dec 5th, 2008, 12:15pm » Quote Modify

on Dec 4th, 2008, 6:56pm, 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...
 IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: A Beastly Number   « Reply #5 on: Dec 5th, 2008, 12:32pm » Quote Modify

2)   10666/5n
n=1
Where in practice the upper bound can be reduced to 666 log 10 / log 5 = 952
 Edit: = 26665666 / 4 + 286 n=1 2666/5n
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
 « Last Edit: Dec 5th, 2008, 1:19pm by SMQ » IP Logged

--SMQ

Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   « Reply #6 on: Dec 6th, 2008, 9:52am » Quote Modify

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.
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: A Beastly Number   « Reply #7 on: Dec 6th, 2008, 12:25pm » Quote Modify

on Dec 6th, 2008, 9:52am, Barukh wrote:
 After working it out, I get the following answer to b): 26645666 - 143.

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

Actually, the approximation 333*log5(2) is pretty good here.
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   Zeros.PNG « Reply #8 on: Dec 7th, 2008, 6:27am » Quote Modify

on Dec 6th, 2008, 12:25pm, Eigenray wrote:
 So is there a clever way to compute the sum of the digits of 2666 = 34004...233245?

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 333*log5(2) 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.
 IP Logged

Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   « Reply #9 on: Dec 7th, 2008, 11:21pm » Quote Modify

I get the following answer to part a):

13407273847...
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: A Beastly Number   « Reply #10 on: Dec 8th, 2008, 7:57am » Quote Modify

on Dec 7th, 2008, 11:21pm, 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 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); }
 « Last Edit: Dec 8th, 2008, 8:21am by Eigenray » IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: A Beastly Number   « Reply #11 on: Dec 8th, 2008, 10:19am » Quote Modify

on Dec 8th, 2008, 7:57am, 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?

 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: A Beastly Number   « Reply #12 on: Dec 8th, 2008, 12:44pm » Quote Modify

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 MPFR:
Code:
 #include #include #include #include   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.)
 « Last Edit: Dec 8th, 2008, 2:00pm by Eigenray » IP Logged
ThudnBlunder
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: A Beastly Number   « Reply #13 on: Dec 9th, 2008, 4:03pm » Quote Modify

My source for this problem got yet a different answer, 1.340727397...
 « Last Edit: Dec 9th, 2008, 4:06pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: A Beastly Number   « Reply #14 on: Dec 9th, 2008, 5:32pm » Quote Modify

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:
 {2} x 10-0.27174945 = 1.340727397,

which is silly.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »