TIFR CSE 2023 | Part B | Question: 9

Question

Fix a positive integer $n$, and let $n=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{k}^{e_{k}}$ be the prime factorization of $n$. Here, $p_{1}, \ldots, p_{k}$ are prime numbers and $e_{i} \geq 1$ for all $1 \leq i \leq k$. Call a sequence $\left(n_{0}, n_{1}, \ldots, n_{t}\right)$ where $n_{0}=n$ and $n_{t}=1$ relevant if for every $0 \leq i \leq t-1,$ the number $n_{i} / n_{i+1}$ is a prime number. What is the total number of relevant sequences?

• A. $\left(p_{1}+1\right) \times\left(p_{2}+1\right) \times \cdots \times\left(p_{k}+1\right)$
• B. $\left(p_{1}+1\right)^{e_{1}} \times\left(p_{2}+1\right)^{e_{2}} \times \cdots \times\left(p_{k}+1\right)^{e_{k}}$
• C. $\left(e_{1}+e_{2}+\cdots+e_{k}\right)$ !
• D. $\frac{\left(e_{1}+e_{2}+\cdots+e_{k}\right) !}{\left(e_{1} !\right) \times\left(e_{2} !\right) \times \cdots \times\left(e_{k} !\right)}$
• E. None of the above

Answer 1

As given $n_0 = n = p_1^{e_1}p_2^{e2}...p_k^{e_k}$.

To get the next number $n_1$ in the relevant sequence, we've to choose $1$ prime number out of $e_1 + e_2 + ... + e_k$ prime numbers and the product of remaining prime numbers will be our $n_1$ and the value $n_0/n_1$ will be that chosen prime number.

We've to repeat this (choose and remove $1$ prime number out from $n_i$ to get $n_{i+1}$) till we exhaust all the prime numbers and we'll get only $n_t = 1$ where $t = e_1 + e_2 + ... + e_k$.

Now, for each relevant sequence there exists an unique sequence of removed prime numbers. So, there is a bijection between relevant sequences and sequences of removed prime numbers.

Consider an example, $n_0 = 60 = 2^2 3^1 5^1$.

Relevant sequence $= 60, 30, 10, 5, 1$.

Corresponding sequence of removed prime numbers $= 2, 3, 2, 5$.

Relevant sequence $= 60, 12, 4, 2, 1$.

Corresponding sequence of removed prime numbers $= 5, 3, 2, 2$.

Total number of prime numbers $= e_1 + e_2 + ... + e_k$.

Of which $e_1$ prime numbers are identical ($p_1$), $e_2$ prime numbers are identical ($p_2$), and so on.

$\therefore$ number of sequences of removed prime numbers $= \frac{(e_1+e_2+...+e_k)!}{(e_1)! + (e_2)! + ... + (e_k)!}$.

Answer :- D.

Comments

nice approach bhai