China Team Selection Test

Let $P(n)$ stand for the biggest prime divisor of $n$, and define $P(1) = f(1) = 1$. We first prove two lemmas.

Lemma 1: For positive integer $n$ and prime $p \mid n$, we have $f(n) \le \sum_{d|\frac{n}{p}} f(d)$.

Proof of Lemma 1: For any factoring of $n$, write $n = n_1 n_2 \cdots n_k$. Since $p \mid n$, there exists $i \in \{1, \cdots, k\}$ such that $p \mid n_i$ (if there are more than one such $i$, choose any one of them), without loss of generality, assume $i = 1$. Map this factoring to a factoring of $d = \frac{n}{n_1}$, $d = n_2 n_3 \cdots n_k$.

For two different factorings of $n$, $n = n_1 n_2 \cdots n_k$ and $n = n'_1 n'_2 \cdots n'_k$ (where $p$ divides $n_1$ and $n'_1$):
- If $n_1 = n'_1$, then $d = n_2 \cdots n_k$ and $d = n'_2 \cdots n'_k$ are two different factorings of $d$ ($d$ is a divisor of $\frac{n}{p}$).
- If $n_1 \ne n'_1$, then $d = \frac{n}{n_1} \ne \frac{n}{n'_1} = d'$, so these two factorings map to a factoring of $d$ and $d'$ respectively ($d$ and $d'$ are divisors of $\frac{n}{p}$).

Thus $f(n) \le \sum_{d|\frac{n}{p}} f(d)$. Lemma 1 is proved.

Lemma 2: For positive integer $n$, let $g(n) = \sum_{d|n} \frac{d}{P(d)}$, then $g(n) \le n$.

Proof of Lemma 2: Induce on the number of different prime divisors of $n$.
- When $n = 1$, $g(1) = 1$.
- When $n = p^a$ is a prime power,
$$g(n) = 1 + 1 + p + \cdots + p^{a-1} = 1 + \frac{p^a - 1}{p-1} \le 1 + p^a - 1 = n.$$

Assume when the number of different prime divisors of $n$ is $k$, we have $g(n) \le n$. Consider the situation when $n$ has $k+1$ different prime divisors. Let the prime factorization of $n$ be $n = p_1^{a_1} \cdots p_k^{a_k} p_{k+1}^{a_{k+1}}$, where $p_1 < \cdots < p_k < p_{k+1}$, and write $n = m p_{k+1}^{a_{k+1}}$. So
$$g(n) = g(m) + \sum_{d|m} \sum_{i=1}^{a_{k+1}} \frac{d p_{k+1}^i}{p_{k+1}} = g(m) + \sigma(m) \frac{p_{k+1}^{a_{k+1}} - 1}{p_{k+1} - 1},$$
where $\sigma(m)$ stands for the sum of positive divisors of $m$. By assumption, $g(m) \le m$.

Since
$$\begin{align*} \sigma(m) \frac{p_{k+1}^{a_{k+1}} - 1}{p_{k+1} - 1} &= \left( \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i - 1} \right) \frac{p_{k+1}^{a_{k+1}} - 1}{p_{k+1} - 1} \\ &\le \left( \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_{i+1} - 1} \right) (p_{k+1}^{a_{k+1}} - 1) \\ &\le \left( \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i} \right) (p_{k+1}^{a_{k+1}} - 1) \\ &\le \left( \prod_{i=1}^k p_i^{a_i} \right) (p_{k+1}^{a_{k+1}} - 1) \\ &= n - m, \end{align*}$$
so $g(n) \le n$. Lemma 2 is proved.

Back to the problem, it is sufficient to prove, for positive integer $n$, $f(n) \le \frac{n}{P(n)}$ holds.

Induce on $n$. When $n=1$, the equality holds. Assume for $n=1, 2, \dots, k$, we have $f(n) \le \frac{n}{P(n)}$. Then when $n=k+1$, by Lemma 1, Lemma 2, and the assumption,
$$f(k+1) \le \sum_{d|\frac{k+1}{P(k+1)}} f(d) \le \sum_{d|\frac{k+1}{P(k+1)}} \frac{d}{P(d)} = g\left(\frac{k+1}{P(k+1)}\right) \le \frac{k+1}{P(k+1)}.$$