Date: 05/17/2003 at 04:46:44 From: Kim Subject: Factorials Hi Dr. Math, I am having trouble finding an algorithm to solve the following problem: What's the least number for x such that x! >= 3^x is true? It's evident in this case that x has to be at least 7, so 7! >= 3^7. But how about if I have a number much greater than 3 for the base of the exponent? I can't keep calculating the factorial and the exponent of a big number. Is there any algorithm to estimate what's the least number? Thank you very much, Kim
Date: 05/17/2003 at 14:35:30 From: Doctor Douglas Subject: Re: Factorials Hi Kim, Thanks for writing to the Math Forum. There is a formula, which is sometimes used to compute an approximation to the factorial, when you don't need an exact answer (i.e. you don't need all of the digits). It is called Stirling's formula: Calculating N factorial http://mathforum.org/library/drmath/view/51556.html The formula is N! ~= sqrt(2*pi*N)*(N^N)*e^(-N) ~= means "approximately" To illustrate the use of this in your problem, we consider the ratio (N!)/(3^N) ~= sqrt(2*pi*N)*e^(-N)*(N/3)^N So we could try to search for the N at which the right-hand side first exceeds 1: sqrt(2*pi*5)*e^-5*(5/3)^5 = 0.486 sqrt(2*pi*6)*e^-6*(6/3)^6 = 0.974 sqrt(2*pi*7)*e^-7*(7/3)^7 = 2.277 thus confirming your calculation. However, this calculation is only an approximation, whereas your calculation is exact (and therefore better). To answer your question about an algorithm, there's nothing wrong with the following algorithm which you've already used for p=3: 1. Choose a guess N. 2. Compute (N!/p^N) by whatever means you see fit. If p is small enough, then a calculator is okay to calculate the factorial. If p is too large, then you will have to use Stirling's formula. 3. If this ratio in (2) is less than 1, then check N+1. If is more than 1, check N-1. This allows you to zero in on the smallest N for which the inequality holds. Remark: You can use the logarithm of Stirling's formula to help keep the numbers from overflowing your calculator: (N!/p^N) > 1 is equivalent to saying log(N!/p^N) > 0 So you must evaluate log(N!/p^N) = log(N!) - N*log(p) = log[sqrt(2*pi*N)*(N^N)*e^(-N)] - N*log(p) = (1/2)log(2*pi*N) + N*log(N) - N - N*log(p) = (1/2)log(2*pi) + (1/2 + N)*log(N) - N*[1+log(p)] and see whether this quantity is positive or not. Note that the logarithm can be taken in any base. - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/
Date: 05/18/2003 at 10:31:00 From: Kim Subject: Thank you (Factorials) Dear Doctor Douglas, Thanks for solving my puzzles. Stirling's formula looks really handy. Kim Hsieh
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.