TIFR CSE 2024 | Part B | Question: 3

Question

For any positive integer $\text{N}$, let $\text{p(N)}$ be the probability that a uniformly random number $a \in\{1, \ldots, N\}$ has an odd number of factors (including 1 and the number itself).
Which of the following is true about the function $p: \mathbb{N} \rightarrow \mathbb{R}$ ?

• A. $\lim _{N \rightarrow \infty} p(N)=\frac{1}{2}$.
• B. $p(N)=\Theta\left(\frac{\log N}{N}\right)$.
• C. $p(N)=\Theta\left(\frac{1}{N}\right)$.
• D. $p(N)=\Theta\left(\frac{1}{\sqrt{N}}\right)$.
• E. $p(N)=\Theta\left(\frac{1}{\log N}\right)$.

   

Answer 1

We can prime factorize any number $n$ as

$n = p^a\cdot q^b\cdot r^c ...$

The number of factors of $n$ can be defined as the number of ways to select a subset these prime factors ($x^3$ as prime factor means we have total 4 ways of selecting $x$ in our factor as either $x^0, x^1, x^2, x^3$) as each subset will represent a different factor, so

Number of factors of  $n =(a + 1)(b+1)(c+1)...$

For number of factors to be odd, all of $a, b, c, ...$ have to be even, thus the number has to be a perfect square.

From $1...N$ we have approximately $\sqrt{N}$ perfect squares, so the probability that a uniformly random number $a \in \{1, 2,... ,N\}$ is $\approx\dfrac{\sqrt{N}}{N}$

$\approx \dfrac{1}{\sqrt{N}}$

Comments

A number has an odd number of factors if and only if it is a perfect square.