# What is the highest power of 2 dividing 100!

What is the highest power of 2 dividing 100!

This is what I have so far:

50 multiples of 2

25 multiples of 4

12 multiples of 8

6 multiples of 16

3 multiples of 32

1 multiple of 64

EDIT: giving a highest power of 2^97

am I missing anything here?

-

-
In 1808, Legendre showed what the exact power of a prime p dividing n! is.In 2010 I figured it out too :) – fmunshi Oct 18 '10 at 4:15
For reference: @Adrián's link discusses the de Polignac-Legendre formula. – J. M. May 1 '12 at 8:26
@Adrián Barquero: link is dead:( can you post updated one – Unknown Nov 4 '13 at 17:04

Your list of multiples is correct. But then the total is 97, not 2^97. But good to see some work.

-
I was always doing some work, just not posting it up to save time :) – fmunshi Oct 18 '10 at 4:08
There are 97 factors of 2 in 100, but saying that 2^97 is the largest power of 2 that divides 100! is then correct. I believe that you are taking a different meaning of the word "power" than intended, as I elaborated on in a comment on Log2's answer. – Jonas Meyer Oct 18 '10 at 23:30

You are not missing anything. Using WolframAlpha to factor 100! into primes, we get the answer: 2^97×3^48×5^24×7^16×11^9×13^7×17^5×19^5×23^4×29^3×31^3×37^2×41^2×43^2×47^2×53×59×61×67×71×73×79×83×89×97(239 factors, 25 distinct)

therefore, the highest power of 2 that divides 100! is 2^97.

100!/2^97 = 588971222367687651371627846346807888288472382883312574253249804256440585603406374176100610302040933304083276457607746124267578125

-
I don't think you have interpreted the alpha result correctly. What you give is the factorization of 100! and it shows 97 (not 2^97) factors of 2. 2^(2^97) is rather greater than 100!. – Ross Millikan Oct 18 '10 at 4:20
No, it shows that 2 is a factor of 100! 97 times, which is 2^97. Any divisor of 100! has to be a combination of it's factor primes, no? Therefore, 2^97 is the highest power of 2 dividing 100!. – Log2 Oct 18 '10 at 19:56
97 is not a power of 2. – anon Oct 18 '10 at 20:16
@Ross: I think you have misinterpreted what Log2 intended. "Power" is not being used as a synonym for "exponent". $2^{97}$ is a factor of 100!. It is a power of 2, and the largest one that divides 100!. 97 would be the largest exponent of a power of 2 that divides 100!. "Power" can be ambiguous in this way, but I believe that Log2's meaning is clear, and correct. – Jonas Meyer Oct 18 '10 at 23:27
I see where is the confusion. My main language isn't english, I apologize. – Log2 Oct 19 '10 at 2:04

How to solve this in the easiest way possible...

keep dividing 100 by 2 till you get a value < 2

100 / 2 = 50

50 / 2 = 25

25 / 2 = 12 (forget about the remainder)

12 / 2 = 6

6 / 2 = 3

3 / 2 = 1

now just add up all the quotients 50 + 25 + 12 + 6 + 3 + 1 = 97

the same logic can be applied to find the highest power of any number x that divides n! completely or evenly.

-
@JM I think you're misunderstanding his answer. He is using the fact the exponent of $p$ in $n!$ is $$\lfloor \frac n p\rfloor+\lfloor \frac n {p^2}\rfloor+\cdots+\lfloor \frac n {p^i} \rfloor+\cdots$$ – user21436 May 1 '12 at 16:56
To the OP: I have upvoted this answer, but you may want to add that the formula you're using is that I mention, this would remove the mystery of forgetting the remainder, apart from improving the answer substantially. – user21436 May 1 '12 at 16:57