Take the 2-minute tour ×

If there exists such an $n$ then $n$ must be the highest of power of 2 that divides $n!$. But to find out the highest power we need to increase n for each step until it reaches $n$. Any idea?


share|improve this question
add comment

2 Answers

up vote 16 down vote accepted

The power of 2 that divides n! is $\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor +\lfloor \frac{n}{8} \rfloor + \ldots \lfloor \frac{n}{2^k} \rfloor$ This can never be more than $n-1$, which occurs when $n$ is a power of 2.

share|improve this answer
Thanks! How stupid I was. –  Chan Feb 19 '11 at 1:00
$n = 0$ is valid I suppose... –  Aryabhata Feb 19 '11 at 1:00
add comment

No. Consider the formula due to Legendre: the power of the prime $p$ in the factorization of $n!$ is $\sum_{k=1}^\infty \lfloor n/p^k \rfloor$. In the case $p=2$ you have $\sum_{k=1}^\infty \lfloor n/2^k \rfloor$. But

$$ \sum_{k=1}^\infty \lfloor n/2^k \rfloor < \sum_{k=1}^\infty n/2^k $$

since we can't have $n/2^k$ an integer for all $k$ simultaneously, so at least one term in the left-hand sum is less than the corresponding term in the right-hand sum. And the right-hand sum is just $n$.

However, as you might imagine from the fact that $\lfloor n/2^k \rfloor$ is close to $n/2^k$, the exponent of 2 in $n!$ is pretty close to $n$; in fact it's $n$ minus the number of 1s in the binary expansion of $n$. In fact, if $n$ is a power of 2, then $2^{n-1}|n!$.

share|improve this answer
THe last statement can't be right. For instance $5! = 120$ is not divisible by $16$. Did you mean $2^{n-1} \mid n!$ ? –  Aryabhata Feb 19 '11 at 1:07
I think $2^n|(n+1)!$ is only true for 2^(odd n). If n is even, n+1 won't contribute another factor 2. –  Ross Millikan Feb 19 '11 at 2:02
Moron, you're right. I've changed that. –  Michael Lugo Feb 19 '11 at 3:50
add comment

Your Answer


