The highest power of 2 that will divide n! = ........ and so on. So, let us try to find the smallest n such that n! is a multiple of 2^{20}.
If n = 10, the highest power of 2 that will divide n! = = 5 + 2 + 1 = 8
If n = 20, the highest power of 2 that will divide n! = = 10 + 5 + 2 + 1 = 18
If n = 24, the highest power of 2 that will divide n! = = 12 + 6 + 3 + 1 = 22
{Here we can also see that each successive number is just the quotient of dividing the previous number by 2. As in, = 6, = 3, = 1. This is a further short-cut one can use.}
So the lowest number of n such that n! is a multiple of 2^{20} is 24.
Now, moving on to finding n! that is a multiple of 3. The highest power of 3 that will divide n! = and so on.
When n = 20, the highest power of 3 that can divide 20! = = 6 + 2 = 8
When n = 35, the highest power of 3 that can divide 35! = = 11 + 3 + 1 = 15
When n = 45, the highest power of 3 that can divide 45! = = 15 + 5 +1 = 21
The lowest number n such that n! is a multiple of 3^{20} is 45.
When n takes values from 24 to 44, n! will be a multiple of 2^{20} and not 3^{20}. n can take 21 values totally.
Correct Answer: 21 values
All features of the online course, including the classes, discussion board, quizes and more, on a mobile platform.
Download videos onto your mobile so you can learn on the fly, even when the network gets choppy!