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^{\prime }{n}_2^{\prime }\cdots n_k^{\prime }$ (where $p$ divides $n_1$ and $n_1^{\prime }$): - If $n_1=n_1^{\prime }$, then $d=n_2\cdots n_k$ and $d=n_2^{\prime }\cdots n_k^{\prime }$ are two different factorings of $d$ ($d$ is a divisor of $\frac{n}{p}$). - If $n_1\ne n_1^{\prime }$, then $d=\frac{n}{n_1}\ne \frac{n}{n_1^{\prime }}=d^{\prime }$, so these two factorings map to a factoring of $d$ and $d^{\prime }$ respectively ($d$ and $d^{\prime }$ 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{array}{rl}\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{array}$$ 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)}.$$