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

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
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search