Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Annoying little problem

  1. Aug 19, 2004 #1
    I was looking through some random problems that asked me to prove certain things. The first one, which is larger: 1.000001^(1,000,000) or 2 was simple, but then it asked me to determine which is larger: 300! or 100^300. Any ideas on how to *correctly* arrive at a solution? My guess is 300! is larger.
     
  2. jcsd
  3. Aug 19, 2004 #2
    Maybe you could count the number of digits in the decimal representation of each number? The number of digits in 100^300 = 10^600 is obviously 601. For 300!, try evaluating floor( log_10(300!) ) + 1 by rewriting the logarithm with base e and then using Stirling's approximation.
     
    Last edited: Aug 19, 2004
  4. Aug 19, 2004 #3

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    300! = 300 * 299 * 298 * ... * 2 * 1 = 100^300 * (3 * 2.99 * 2.98 * ... * 0.02 * 0.01)

    Simply evaluate if (3 * 2.99 * 2.98 * ... * 0.02 * 0.01) is smaller or bigger than 1, if it's bigger then 300! is bigger than 100^300

    (This is just a guess, I've never done anything like this before)

    Edit: I just ran a quick program and get it as being about 306057512220160, but I'm not 100% confident I am right.
     
    Last edited: Aug 19, 2004
  5. Aug 19, 2004 #4

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Here's a way:

    the number of digits in 300^100 is [100log 300] = 247 (log is the base-10 logarithm and the square brackets signify the floor function)

    therefore if 300! > 300!, the numebr of digits in 300! will be greater than 247.

    The number of digits in 300! is:

    [tex]\sum^{300}_{i=1} \log{i}[/tex]

    as for any k > 100 we know that log k > 2

    We know the last 200 terms in the sum are greater than or equal to 2, meaning the sum of the last 200 terms is at least 400. Therfore 300! has at least 400 digits and is greater than 300^100.

    edited to add: oops I've got the digits the wrong way round, I'll have anothe rllok at it.
     
    Last edited: Aug 19, 2004
  6. Aug 19, 2004 #5

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Hmm I've looked at it agin, ther's no easy way of usig the method above to prove that 300! > 100^300 (which it is, but only by 14 orders which isn't much in this context).
     
  7. Aug 19, 2004 #6

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    jcsd I really like that way, however [itex]100^{300}[/itex] = [itex](10^2)^{300}[/itex] = [itex]10^{600}[/itex].

    If my method is correct then it should stand that:

    [tex]\left(\sum^{300}_{i=1} \log_{10}{i}\right) - 15 \approx 600[/tex]

    And therefore:

    [tex]\left(\sum^{300}_{i=1} \log_{10}{i}\right) \approx 615[/tex]

    Running through a quick program I just made I get that:


    [tex]\sum^{300}_{i=1} \log_{10}{i} \approx 614.485803[/tex]

    Thus showing that my method agrees with your method and 300! > 100^300
     
  8. Aug 19, 2004 #7

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Yep I misread 100^300 as 300^100. There's no easy way though of proving it using that method tho' without using a computer.
     
  9. Aug 19, 2004 #8

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Well I've been putting this into my calculator, I would struggle doing it on paper.
     
  10. Aug 19, 2004 #9

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Infact the Stirling approximation seems the best way to go as you can prove quite easily it's larger than 10^614.
     
  11. Aug 19, 2004 #10
    log( 100^300 ) = 600

    log( 300! ) approx log [ sqrt(2*pi*300) * (300/e)^300 ]

    = 1.6377 + 300 * 2.0428 = 614.4857

    So, 300! > 100^300
     
  12. Aug 19, 2004 #11
    Thanks for all the replies.. Just a little background information on the problem: it is over 50 years old so it must have a non-computer-oriented solution. Any ideas with this new info? I considered the logarithmic method before I posted this but wasn't satisfied with the results because they seemed too contrived by the calculator.
     
  13. Aug 19, 2004 #12

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Rogerio's solution is failry starightforawrd , can be done on a piece of paper and is correct (300! must actually be smaller than the solution obtained by Rogerio, though infact it's only a 'little' bit smaller).
     
    Last edited: Aug 19, 2004
  14. Aug 19, 2004 #13

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Rogerio's use of Stirlings can be done by hand, but you need to have an idea of how far off the Stirlings approximation is at 300! (this is certainly do-able, and the answer is it's certainly not far enough to affect the result). You don't need quite the power of Stirling though, you can bound log(300!) accurately enough from below by an integral:

    [tex]\log(300!)=\sum\limits_{n=1}^{300}\log(n)\geq\int\limits_{1}^{300}\log(t)dt=300\log (300)-300+1> 300(\log(300)-1)= 300\log (300/e)> 300\log(100)=\log(100^{300})[/tex]

    And you're done.
     
  15. Aug 19, 2004 #14
    Bravo!

    -- AI
     
  16. Aug 20, 2004 #15
    Great solution shmoe. I just found the solution given in the particular problem set and it's radically different but I have to say yours is much simpler.
     
  17. Aug 20, 2004 #16

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Actually the formula Rogerio used is guarenteed to be less than 300!, so it is simply sufficent to prove thta the approximation given by Rogrio is greater than 100^300, which it is.
     
  18. Aug 20, 2004 #17

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    I find people often forget the power of a log table :smile:
     
  19. Aug 20, 2004 #18

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Good to know! My day to day dealings with stirlings approx. is for asymptotics in the complex plane. I'd never bothered to consider that it would always be an under approximation for real values.


    vsage, what method did the solutions use?
     
  20. Aug 20, 2004 #19
    It seems ok :-)
     
    Last edited: Aug 20, 2004
  21. Aug 20, 2004 #20

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You'll notice [tex]0.301\geq -0.397[/tex], which agrees with the inequality I posted.

    We have:

    [tex]\log(n)=\int\limits_{n-1}^{n}\log(n)dt\geq\int\limits_{n-1}^{n}\log(t)dt[/tex]

    since log is increasing on [tex](n-1,n)[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Annoying little problem
  1. A weird little problem (Replies: 1)

  2. A little problem (Replies: 9)

  3. A little problem (Replies: 7)

Loading...