Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I think where you say "estimates" you mean "bounds"? –  joriki Sep 28 '12 at 3:43

2 Answers 2

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.

share|improve this answer
1  
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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.