# How many bits are in factorial?

I am interested in good integer approximation from below and from above for binary Log(N!). The question and the question provides only a general idea but not exact values. In other words I need integers A and B so that A <= Log(N!) <= B

-
I think where you say "estimates" you mean "bounds"? –  joriki Sep 28 '12 at 3:43

The Wikipedia article on Stirling's approximation gives the bounds

$$\sqrt{2\pi}\ n^{n+1/2}\mathrm e^{-n} \le n! \le \mathrm e\ n^{n+1/2}\mathrm e^{-n}\;,$$

so with $g(n)=((n+\frac12)\log n-n)$ we have

$$\lfloor (g(n)+\log\sqrt{2\pi})/\log2\rfloor\le d(n)-1\le\lfloor (g(n)+1)/\log2\rfloor\;,$$

where $d(n)$ is the number of binary digits of $n!$ before the binary point.

-
See also mathoverflow.net/questions/19170/… for a discussion of the story in base 10, with references to the situation in other bases. –  Gerry Myerson Sep 28 '12 at 6:10
@Gerry: I never quite understand what gets closed on MO and what doesn't. This doesn't seem particularly researchy to me :-) –  joriki Sep 28 '12 at 7:58
sure, MO is inconsistent on what gets closed, but I think there was a serious research question there. That the formula was very good is not researchy, but whether the formula was perfect took some thought and some work. –  Gerry Myerson Sep 28 '12 at 9:21

Expanding on joriki's answer, taking more terms from the approximation, $$\log (n!) = n(\log n - \log e) + \frac{1}{2}\log n + \log \sqrt{2\pi} + \frac{\log e}{C_ n}, \quad 12n < C_n < 12n+1.$$ The number of binary digits is equal to $\lceil \log n! \rceil$, and for most $n$, I expect that the slight uncertainty in $C_n$ won't effect $\lceil \log n! \rceil$.

-
The number of binary digits is $\lfloor\log n!\rfloor+1$: If the result is an integer you need one more digit, so you can't use the ceiling function. –  joriki Sep 28 '12 at 3:55