Friday, July 22, 2016

elementary number theory - What is the largest power of 2 that divides $200!/100!$.





What is the largest power of 2 that divides $200!/100!$.



No use of calculator is allowed.
I had proceeded in a brute force method which i know regret..
I would like to know your methods.



Answer



Find highest power of $2$ in $200!$ and $100!$, using Legendre's formula



In $200!$, highest power of $2$



$$=\lfloor 200/2 \rfloor +\lfloor 200/4 \rfloor +\lfloor 200/8 \rfloor +\lfloor 200/16 \rfloor +\lfloor 200/32 \rfloor +\lfloor 200/64 \rfloor +\lfloor 200/128 \rfloor $$



$$=100+50+25+12+6+3+1=197$$



In $100!$, highest power of $2$




$$=\lfloor 100/2 \rfloor +\lfloor 100/4 \rfloor +\lfloor 100/8 \rfloor +\lfloor 100/16 \rfloor +\lfloor 100/32 \rfloor +\lfloor 100/64 \rfloor$$



$$= 50 + 25+12+6+3+1 =97$$



Now, just subtract the two, and we get $100$ as the answer.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...