$p(m)$ is the number of distinct prime divisors of a positive integer $m>1$ and $f(m)$ is the $\bigg \lfloor \frac{p(m)+1}{2}\bigg \rfloor$ th smallest prime divisor of $m$. Find all positive integers $n$ satisfying the equation: $$f(n^2+2) + f(n^2+5) = 2n-4$$
Problem
Source: Turkey EGMO TST 2020 P2
Tags: function, number theory
kaede
06.02.2020 13:20
Since $2+3\leq f\left( n^{2} +2\right) +f\left( n^{2} +5\right) =2n-4$, we have $n\geq 5$.
For $n=5$, $f( 27) +f( 30) =3+3=2\cdotp 5-4$, so $n=5$ satisfies the equation.
Assume, for the sake of contradiction, that $n\geq 6$ satisfies the given equation.
So we have $f\left( n^{2} +2\right) +f\left( n^{2} +5\right) =2n-4\cdots ( \heartsuit )$
First, we can verify that $f\left( n^{2} +2\right) \neq n,n-1\cdots ( \clubsuit )$ and $f\left( n^{2} +5\right) \neq n-1,n-2\ \cdots ( \diamondsuit )$ as follows:$ $
If $n=f\left( n^{2} +2\right)$, then $n\mid n^{2} +2\Rightarrow \ n\mid 2$, impossible.
If $n-1=f\left( n^{2} +2\right)$, then $n-1\mid n^{2} +2\Rightarrow \ n-1\mid 3$, impossible.
If $n-2=f\left( n^{2} +5\right)$, then $n-2\mid n^{2} +5\ \rightarrow \ n-2\mid 9$, impossible.
If $n-1=f\left( n^{2} +5\right)$, then $n-1\mid n^{2} +5\ \rightarrow \ n-1\mid 6$, impossible.
We consider the following two cases $( 1) ,( 2)$.
$( 1) \ \ 2\mid n^{2} +2$
In this case, $p\left( n^{2} +2\right) \geq 2$ because $4 \nmid n^2+2$.
If $n\leq f\left( n^{2} +2\right)$, then $n( n+2) \leq n^{2} +2$, impossible,
So we must have $f\left( n^{2} +2\right) \leq n-2$ from $( \clubsuit )$.
It follows from $( \heartsuit )$ that $f\left( n^{2} +5\right) \geq n-2$ .
So we must have $f\left( n^{2} +5\right) \geq n$ from $( \diamondsuit )$.
If $p\left( n^{2} +5\right) \geq 2$, then $n^{2} +5\geq n( n+2)$, impossible.
So we we must have $p\left( n^{2} +5\right) =1$.
It follows that there exist $k\in \mathbb{N}$ such that $n^{2} +5=q^{k}$ where $q$ is a prime and $q\geq n+1$.
Since $n^{2} +5< ( n+1)^{2}$, we must have $k=1$.$ $
However, we have $f\left( n^{2} +5\right) =n^{2} +5$, and this is clearly impossible.
$( 2) \ \ 2\mid n^{2} +5$
In this case, $p\left( n^{2} +5\right) \geq 2$ because $4 \nmid n^2+5$.
If $n\leq f\left( n^{2} +5\right)$, then $n( n+2) \leq n^{2} +5$, impossible,
So we must have $f\left( n^{2} +5\right) \leq n-3$ from $( \diamondsuit )$.
It follows from $( \heartsuit )$ that $f\left( n^{2} +2\right) \geq n-1$.
So we have $f\left( n^{2} +2\right) \geq n+1$ from $( \clubsuit )$.
If $p\left( n^{2} +2\right) \geq 2$, then $n^{2} +2\geq ( n+1)( n+3)$, impossible.
So we we must have $p\left( n^{2} +2\right) =1$.
It follows that there exist $k\in \mathbb{N}$ such that $n^{2} +2=q^{k}$ where $q$ is a prime and $q\geq n+1$.
Since $n^{2} +2< ( n+1)^{2}$, we must have $k=1$.$ $
However, we have $f\left( n^{2} +2\right) =n^{2} +2$, and this is clearly impossible.
Conclusion: $n$ satisfies the given equation if and only if $\boxed{n=5}$.
grupyorum
18.02.2020 17:19
Check the cases $n=1,2,\dots,7,8$ manually to see $n=5$ is the only one among them satisfying the condition. Furthermore, if either $n^2+2$ or $n^2+5$ is a prime, left hand side is bigger than right hand size. The key idea is the following: $f(n)\leqslant \sqrt{n}$ for every composite $n$. To see this, if $n$ is a prime power, the conclusion follows immediately. If $n$ is not a prime power, and $f(n)>\sqrt{n}$, it also follows that $p(m)^{th}$ (distinct) prime divisor of $n$ is also larger than $\sqrt{n}$, a contradiction. Equipped with this, we now attack the problem. If $f(n^2+2)=n$ then $n\mid n^2+2$, that is, $n\mid 2$, handled already. If $f(n^2+2)=n-1$ then $n-1\mid n^2+2$ and thus $n-1\mid 3$, $n\leqslant 4$, also handled already. Finally, if $f(n^2+2)=n-2$, then $n-2\mid n^2+2$ and thus $n-2\mid 6$, handled already. Thus $f(n^2+2)\leqslant n-3$. Similarly, if $f(n^2+5)=n$, then $n\mid n^2+5$, that is $n\mid 5$, handled already. If $f(n^2+5)=n-1$ then $n-1\mid n^2+5$, implying $n-1\mid 6$, that is $n\leqslant 7$ handled already. Thus $f(n^2+5)\leqslant n-2$ and $f(n^2+2)\leqslant n-3$, and thus $f(n^2+2)+f(n^2+5)<2n-4$. Thus, $n=5$ is the only possibility.