ohwell wrote:
I would have interpreted it as 20!/2^k, so, I would think I need to know what 20! is. Then I would have tried different values for k that would hopefully be close to whatever the value of 20! is. I realize this is nuts. I don't want to calculate 20! and I bet no one wants to.
So, how come I can just use 20 instead of 20! ?
I don't understand I can do what you suggest:
"Divide 20 by increasing powers of 2 till u get 0 as the integer quotient and add all the integer quotients in the process"
If prime factorizations are relatively new to you, the question in the post above is not a good place to start - better to start with something easier. In questions about divisibility, you almost always want to get a prime factorization. That is, we certainly do not want to work out what 20! is equal to by multiplying it out for this question - instead we want to break it down into its prime divisors. If we have a prime factorization of 20!, we'll be able to answer the question; to illustrate, suppose instead you had the following (easier) question:
What is the greatest integer k for which 2^k is a factor of 2^18 * 3^7 * 5^4 ?
The answer would then be k = 18, since 2^18 * 3^7 * 5^4 is divisible by 2^18 but is not divisible by 2^19.
Thus, getting back to the original question, when they ask:
What is the greatest integer k for which 2^k is a factor of 20! ?
we can rephrase the question as:
What is the exponent on the 2 in the prime factorization of 20! ?
cramya offers a shortcut for answering this, but let's first do this the long way. 20! = 20*19*18*17*.... When we break these down into primes, we'll only get 2's from the even numbers, so if we prime factorize:
20*18*16*14*12*10*8*6*4*2
we'll get the answer. We only care about the prime factor 2; looking at the above, and working out how many 2's each of the numbers gives us we have:
(2^2)*(2^1)*(2^4)*(2^1)*(2^2)*(2^1)*(2^3)*(2^1)*(2^2)*(2^1) = 2^18
where the first 2^2 comes from 20, then 2^1 comes from 18, then 2^4 comes from 16, etc.
cramya's shortcut works for the following reason:
-we are multiplying all the positive even integers up to 20;
-each even integer will contribute at least one to the power of 2 in the prime factorization of 20!. We have 20/2^1 = 10 even integers up to 20;
-each multiple of 2^2 will contribute one additional 2 that we haven't yet counted; there will be 20/2^2 = 5 multiples of four up to 20;
-each multiple of 2^3 will contribute yet another 2 that we haven't yet counted; there will be 20/2^3 (ignore the remainder) = 2 multiples of eight up to 20;
-finally, each multiple of 2^4 will contribute another 2 we haven't counted, and there will be 20/2^4 (ignore the remainder) = 1 multiple of sixteen up to 20.
Adding, we get 10 + 5 + 2 + 1 = 18.
