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.

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

share|improve this question

2 Answers 2

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
9  
$n = 0$ is valid I suppose... –  Aryabhata Feb 19 '11 at 1:00

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
2  
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
1  
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

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.