# CAT Practice : Number System: Factorial

You are here: Home  CAT Questionbank   CAT Quant  Number System: Factorial  Question 4
Finding the highest power of 3 that divides n! is easy. Find the smallest n such that n! is a multiple of 3^k might not be easy. Think about that.

## Factorials - basic

Q.4: How many values can natural number n take, if n! is a multiple of 220 but not 320?
1. 11
2. 21
3. 16
4. 5

Choice B. 21

## Detailed Solution

The highest power of 2 that will divide n! = $\left[ {{{\rm{n}} \over {\rm{2}}}} \right]{\rm{ + }}\left[ {{{\rm{n}} \over {\rm{4}}}} \right]{\rm{ + }}\left[ {{{\rm{n}} \over {\rm{8}}}} \right]{\rm{ + }}\left[ {{{\rm{n}} \over {{\rm{16}}}}} \right]$........ and so on. So, let us try to find the smallest n such that n! is a multiple of 220.

If n = 10, the highest power of 2 that will divide n! = $\left[ {{{{\rm{10}}} \over {\rm{2}}}} \right]{\rm{ + }}\left[ {{{{\rm{10}}} \over {\rm{4}}}} \right]{\rm{ + }}\left[ {{{{\rm{10}}} \over {\rm{8}}}} \right]$ = 5 + 2 + 1 = 8

If n = 20, the highest power of 2 that will divide n! = $\left[ {{{{\rm{20}}} \over {\rm{2}}}} \right]{\rm{ + }}\left[ {{{{\rm{20}}} \over {\rm{4}}}} \right]{\rm{ + }}\left[ {{{{\rm{20}}} \over {\rm{8}}}} \right]{\rm{ + }}\left[ {{{{\rm{20}}} \over {{\rm{16}}}}} \right]$ = 10 + 5 + 2 + 1 = 18

If n = 24, the highest power of 2 that will divide n! = $\left[ {{{{\rm{24}}} \over {\rm{2}}}} \right]{\rm{ + }}\left[ {{{{\rm{24}}} \over {\rm{4}}}} \right]{\rm{ + }}\left[ {{{{\rm{24}}} \over {\rm{8}}}} \right]{\rm{ + }}\left[ {{{{\rm{24}}} \over {{\rm{16}}}}} \right]$ = 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, $\left[ {{{{\rm{12}}} \over {\rm{2}}}} \right]$ = 6, $\left[ {{{{\rm{6}}} \over {\rm{2}}}} \right]$ = 3, $\left[ {{{{\rm{3}}} \over {\rm{2}}}} \right]$ = 1. This is a further short-cut one can use.}

So the lowest number of n such that n! is a multiple of 220 is 24.

Now, moving on to finding n! that is a multiple of 3. The highest power of 3 that will divide n! = $\left[ {{{\rm{n}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{\rm{n}} \over {\rm{9}}}} \right]{\rm{ + }}\left[ {{{\rm{n}} \over {{\rm{27}}}}} \right]{\rm{ + }}\left[ {{{\rm{n}} \over {{\rm{81}}}}} \right]$ and so on.

When n = 20, the highest power of 3 that can divide 20! = $\left[ {{{{\rm{20}}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{\rm{6}} \over {\rm{3}}}} \right]$ = 6 + 2 = 8
When n = 35, the highest power of 3 that can divide 35! = $\left[ {{{{\rm{35}}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{{\rm{11}}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{\rm{3}} \over {\rm{3}}}} \right]$ = 11 + 3 + 1 = 15
When n = 45, the highest power of 3 that can divide 45! = $\left[ {{{{\rm{45}}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{{\rm{15}}} \over {\rm{3}}}} \right]{\rm{ + }}\left[ {{{\rm{5}} \over {\rm{3}}}} \right]{\rm{ }}$ = 15 + 5 +1 = 21

The lowest number n such that n! is a multiple of 320 is 45.

When n takes values from 24 to 44, n! will be a multiple of 220 and not 320. n can take 21 values totally.

## Our Online Course, Now on Google Playstore!

### Fully Functional Course on Mobile

All features of the online course, including the classes, discussion board, quizes and more, on a mobile platform.

### Cache Content for Offline Viewing

Download videos onto your mobile so you can learn on the fly, even when the network gets choppy!

## More questions from Number System - Factorial

This idea is so good that it comes with an exclamation mark. N! holds marvels that you might not have noticed before. Enter here to see those.