Arithmetic Function

We shall show below that $f(3) = 3$ . Assuming that, we can show that $f(n) = n$ for al $n \ge 1$ . Now $f(6) =f(2)f(3) = 6$ and so $3 < f(4) < f(5) < 6$ , so that $f(4) = 4,f(5)= 5$ . Certainly, then, $f(j) = j$ for all $1 \le j \le 5$ .

Suppose inductively that $f(j) = j$ for all $1 \le j \le 4n+1$ . Then $4n+6 = 2(2n+3)$ and $2n+3 \le 4n+1$ , so that $f(4n+6) = f(2)f(2n+3) = 4n+6$ , and hence $4n+1 = f(4n+1) < f(4n+2) < f(4n+3) < f(4n+4) < f(4n+5) < 4n+6$ so that $f(4m+2) = 4n+2$ , $f(4n+3) = 4n+3$ , $f(4n+4) = 4n+4$ and $f(4n+5) = 4n+5$ . Thus we have shown that $f(j) = j$ for all $1 \le j \le 4n+5$ . Thus we deduce by induction that $f(j) = j$ for all $j \ge 1$ . Thus the only possible value of $f(17)$ is $\boxed{17}$ .

It remains to show that $f(3) = 3$ .

• Suppose first that $f(3) = 4$ . Then $f(4) \ge 5$ , $f(5) \ge 6$ , and hence $f(60) = f(3)f(4)f(5) \ge 120$ . On the other hand, $f(6) = f(2)f(3) = 8$ , so $f(5) \le 7$ , so $f(10) =f(2)f(5) \le 14$ , so $f(9) \le 13$ , so $f(18) = f(2)f(9) \le 26$ , so $f(17) \le 25$ , so $f(34) = f(2)f(27) \le 50$ , so $f(33) \le 49$ , so $f(66) = f(2)f(33) \le 98$ , and hence $f(60) \le 92$ . This contradiction implies that $f(3) \neq 4$ .

• Suppose that $f(3) = n \ge 5$ . Then $f(4) \ge n+1$ , $f(5) \ge n+2$ , and hence $f(60) \ge n(n+1)(n+2) \ge 42n$ . On the other hand $f(6) = 2n$ , so $f(5) \le 2n-1$ , so $f(10) \le 4n-2$ , so $f(9) \le 4n-3$ , so $f(18) \le 8n-6$ , so $f(17) \le 8n-7$ , so $f(34) \le 16n-14$ , so $f(33) \le 16n-15$ , so $f(66) \le 32n-30$ , so $f(60) \le 32n - 36 \le 32n$ . This contradiction shows that this option is impossible as well.

Thus we must have $f(3) = 3$ , and so the proof is complete.

Note that, $f(2^m + 1) \leq f(2(2^{m-1} + 1)) = 2 f(2^{m-1} + 1) \leq ... = 2^m f(2) = 2^{m+1}$

Also, for any $x$ , we can find $m$ such that $2^m \leq x \leq 2^{m+1}$ . Thus $2x \geq 2^{m+1}$ and $f(x) \leq f(2^{m+1} + 1) \leq 2^{m+2}$

$\implies \dfrac{f(x)}{x} \leq 4$

Now, assume that $f(x) \neq x$ . So, there is some $k > 2$ such that $f(k) \neq k$ . Since $f$ is strictly increasing, it follows that $f(k) > k$ and $f(x) > x \ \forall \ x \geq k$

Denote the primes greater than $k$ as $p_1, p_2, p_3, \ldots$ . Define $c_n = p_1 \cdot p_2 \cdot \ldots \cdot p_n$

Now, $f(p_i) \geq p_i + 1$ for any $p_i$ since $f(x) > x \ \forall \ x \geq k$ . So, we have,

$f(c_n) = f(p_1) ... f(p_n) \geq (p_1 + 1) ... (p_n + 1)$

$\implies \dfrac{f(c_n)}{c_n} \geq \left(1 + \dfrac{1}{p_1} \right) \cdot \left(1 + \dfrac{1}{p_2} \right) \cdot \ldots \cdot \left(1 + \dfrac{1}{p_n} \right) \geq \left(\dfrac{1}{p_1} + \dfrac{1}{p_2} + \ldots + \dfrac{1}{p_n}\right) + \ldots$

Since the sum of the reciprocals of the prime numbers diverges and only finitely many primes are missing, it follows that the product on the RHS diverges as $n \to \infty$ . Thus the sequence $\dfrac{f(c_n)}{c_n} \to \infty$ , which is impossible for the bounded sequence $\dfrac{f(c_n)}{c_n}$ .

$\therefore f(x) = x \ \forall \ x \in \mathbb{N}$

$f(15)<f(18)$

$f(3)f(5)<2f(9)<2f(10)=4f(5)$

$2<f(3)<4$

$f(3)=3$

$f(6)=6$ , so we must have $f(n)=n$ for $n=4,5$

$f(30)=30$ , so $f(17)=17$