4
$\begingroup$

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

  • 0
    I think where you say "estimates" you mean "bounds"?2012-09-28

2 Answers 2

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.

  • 0
    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.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$.

  • 1
    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.2012-09-28