IMO Hk TST

Number theory Difficulty 8.3 Shortlist Prove it Hong Kong

Denote by $\sigma(n)$ the sum of divisors of $n$ . A positive integer $n$ ( $n \ge 2$ ) is redundant if for any integer $k$ , with $k < n$ , we have $\frac{\sigma(k)}{k} < \frac{\sigma(n)}{n}$ . (For instance if $n = 1, 2, 3, 4, 5$ , then $\frac{\sigma(n)}{n} = 1, \frac{3}{2}, \frac{4}{3}, \frac{7}{4}, \frac{6}{5}$ respectively. Hence, $2$ and $4$ are redundant, $3$ and $5$ are not.) Show that there exist infinitely many redundant numbers.

Solution

(Superabundant numbers/IMO Shortlist 1983) When $n = m!$ , we have
$\frac{\sigma(m!)}{m!} \ge \frac{1}{m!} \left( m! + \frac{m!}{2} + \frac{m!}{3} + \dots + \frac{m!}{m} \right) = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{m}.$
Since the harmonic series diverges, the sequence $\left\{ \frac{\sigma(n)}{n} \right\}$ is unbounded. Therefore, after finding some redundant numbers $n_1, n_2, \dots, n_k$ , we can always find the next number $n_{k+1}$ such that $\frac{\sigma(n_{k+1})}{n_{k+1}} > \frac{\sigma(n_k)}{n_k}$ . This implies $n_{k+1}$ is redundant, and so there are infinitely many redundant numbers.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.