TIFR CSE 2011 | Part A | Question: 15

Question

The exponent of $3$ in the product $100!$ is

• A. $27$
• B. $33$
• C. $44$
• D. $48$
• E. None of the above

Answer 1

Exponent of $p$ in $n!$, where $p$ is a prime number, and $n$ is an integer greater than $p$ is: $$E_p (n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots + \left\lfloor \frac{n}{p^S} \right\rfloor$$ where $S$ is the largest positive integer such that $p^s \leq n \leq p^{s+1}$

So, $$\begin{align} E_3(100!) &= \left\lfloor \frac{100}{3} \right\rfloor + \left\lfloor \frac{100}{3^2} \right\rfloor + \left\lfloor \frac{100}{3^3} \right\rfloor + \left\lfloor \frac{100}{3^4} \right\rfloor+ \left\lfloor \frac{100}{3^5} \right\rfloor \\[1em] &= 33+11+3+1+0\\&= 48\end{align}$$Correct Answer: $D$

Comments

Can you explain how the formula works...

---

3$^{1}$ factors must be counted once.

3$^{2}$ factors must be counted twice.

3$^{3}$ factors must be counted thrice.

.

.

.

and so on.

---

So the formula would be to add all the below:

$\left \lfloor \frac{100}{3^{1}} \right \rfloor$ ----> counts all factors of 3$^{1}$ once.

$\left \lfloor \frac{100}{3^{2}} \right \rfloor$ -----> counts all factors of 3$^{2}$ once more (making it twice)

$\left \lfloor \frac{100}{3^{3}} \right \rfloor$ -----> counts all factors of 3$^{3}$ once more (making it thrice)

$\left \lfloor \frac{100}{3^{4}} \right \rfloor$ -----> counts all factors of 3$^{4}$ once more (making it four times)

$\left \lfloor \frac{100}{3^{5}} \right \rfloor$ -----> counts all factors of 3$^{5}$ once more (making it five times)

---

This formula is only applicable when n is greater than p, and also p is a prime number.

Ex: The exponent of 10 in the product of 5! cannot be obtained with the above formula.

As per the formula we would get zero as the answer.

But actually 1 would be the correct answer as 5! = 120.

(A very nice solution given in Geeks for Geeks)

Answer 2

The formula in the sonu's answer can be represented as

Answer 3

In n! , we have factors that are multiples of 3,9,27,81,243,….. If we divide them by 3(9,18,27,36,45,...)we get (3,6,9,12,15..), still multiples of 3. This means that we still have  power of 3’s that needs an even pair, so we need to divide again by 3.

Now, since we have already counted the 3’s in the first division, we need to count the second set of 3’s. Instead of dividing again by 3, we divide them by 9 and next by 27 and so on. That is the reason why we also divide n by powers of 3.

 Count of 3s in n! = floor(n/3) + floor(n/9) + floor(n/27) + floor(n/81) +….

                                       =   $\left \lfloor \frac{100}{3} \right \rfloor$ +$\left \lfloor \frac{100}{9} \right \rfloor$ + $\left \lfloor \frac{100}{27} \right \rfloor$ + $\left \lfloor \frac{100}{81} \right \rfloor$ + $\left \lfloor \frac{100}{243} \right \rfloor$ 

                                       =    33  +  11  +  3  + 1 + 0

                                       =    48

answer is option D