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
How many bits are in factorial?
4
$\begingroup$
approximation
factorial
-
0I think where you say "estimates" you mean "bounds"? – 2012-09-28
2 Answers
6
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.
-
1See also http://mathoverflow.net/questions/19170/how-good-is-kamenetskys-formula-for-the-number-of-digits-in-n-factorial for a discussion of the story in base 10, with references to the situation in other bases. – 2012-09-28
-
0@Gerry: I never quite understand what gets closed on MO and what doesn't. This doesn't seem particularly researchy to me :-) – 2012-09-28
-
0sure, 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. – 2012-09-28
2
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$.
-
1The 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. – 2012-09-28