Stirling's Formula

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