The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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 

Thank you very much,

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 

   Calculating N factorial 

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 

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 

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
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.