Annoying little problem

1. Aug 19, 2004

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.

2. Aug 19, 2004

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.

Last edited: Aug 19, 2004
3. Aug 19, 2004

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.

Last edited: Aug 19, 2004
4. Aug 19, 2004

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.

Last edited: Aug 19, 2004
5. Aug 19, 2004

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

6. Aug 19, 2004

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

7. Aug 19, 2004

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.

8. Aug 19, 2004

Zurtex

Well I've been putting this into my calculator, I would struggle doing it on paper.

9. Aug 19, 2004

jcsd

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

10. Aug 19, 2004

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

11. Aug 19, 2004

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.

12. Aug 19, 2004

jcsd

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
13. Aug 19, 2004

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.

14. Aug 19, 2004

TenaliRaman

Bravo!

-- AI

15. Aug 20, 2004

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.

16. Aug 20, 2004

jcsd

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.

17. Aug 20, 2004

Zurtex

I find people often forget the power of a log table

18. Aug 20, 2004

shmoe

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?

19. Aug 20, 2004

Rogerio

It seems ok :-)

Last edited: Aug 20, 2004
20. Aug 20, 2004

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