6
$\begingroup$

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?

Thanks,
Chan

2 Answers 2

16

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.

  • 9
    $n = 0$ is valid I suppose...2011-02-19
10

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!$.

  • 0
    Moron, you're right. I've changed that.2011-02-19