4
$\begingroup$

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?

4 Answers 4

2

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

  • 0
    I was always doing some work, just not posting it up to save time :)2010-10-18
  • 1
    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.2010-10-18
1

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

  • 0
    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!.2010-10-18
  • 0
    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!.2010-10-18
  • 1
    97 is not a power of 2.2010-10-18
  • 3
    @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.2010-10-18
  • 0
    I see where is the confusion. My main language isn't english, I apologize.2010-10-19
  • 0
    @Log2: No need to apologize, your writing is very clear. This isn't a problem with your usage, but with English itself. Sometimes, like in Adrian's link, power is used to mean the exponent (unfortunately I think), but it is entirely standard to call $p^n$ a power of $p$.2010-10-19
  • 0
    I think that in this case it's even worse because, in addition to that, 2^97 and 97 are factors of 100! which may be the reason of muad's comment, perhaps.2010-10-19
  • 0
    Good point, but it's also even worse because I think that muad was objecting to Ross's use of "power" to mean "exponent", but it might not have been clear to either one what the others' objections were.2010-10-19
1

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.

  • 0
    @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$$2012-05-01
  • 0
    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.2012-05-01
1

@Adrián Barquero's link is dead, and I don't have the rep to comment, so here's the archive link from 2008:

http://web.archive.org/web/20080430101233/http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html

  • 0
    Thank you, I have added the link under Adrian's answer. Ideally, you could edit your answer and quote the most relevant part of the link. That would be great especially if the link dies again. Then, we could flag Adrian's answer and keep your.2017-02-13
  • 0
    Also, your link does unfortunately not render the latex.2017-02-13