Annoying little problem

[vsage]

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.

[Muzza]

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.

[Zurtex]

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.

[jcsd]

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:

\sum^{300}_{i=1} \log{i}

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.

[jcsd]

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).

[Zurtex]

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

If my method is correct then it should stand that:

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

And therefore:

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

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


\sum^{300}_{i=1} \log_{10}{i} \approx 614.485803

Thus showing that my method agrees with your method and 300! > 100^300

[jcsd]

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.

[Zurtex]

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.
Well I've been putting this into my calculator, I would struggle doing it on paper.

[jcsd]

Infact the Stirling approximation seems the best way to go as you can prove quite easily it's larger than 10^614.

[Rogerio]

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

[vsage]

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.

[jcsd]

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.

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).

[shmoe]

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:

\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})

And you're done.

[TenaliRaman]

Bravo!

-- AI

[vsage]

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.

[jcsd]

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:

\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})

And you're done. 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.

[Zurtex]

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.
I find people often forget the power of a log table :smile:

[shmoe]

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.

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?

[Rogerio]

It seems ok :-)

[shmoe]

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

We have:

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

since log is increasing on (n-1,n)

[vsage]

Shmoe: the solution is over a page long, but it involved first proving that the product of n consecutive natural numbers is greater than the nth power of the square root of the product of the first and last number (almost verbatim). It's really way too long to type out right now, but I guess if you're interested I'll type it up tomorrow.

[shmoe]

The general idea is good enough vsage, I can fill in the details on my own. You can find a more interesting use of your time:).