Team Selection Test for IMO 2023

Answer: Yes, there exists.

Observation 1: If $p$ is the smallest prime divisor of $n=px$, then $f(n)=n-x=x(p-1)$.

Observation 2: Let $p$ be a prime number and $x$ be a positive integer. If $x=1$ or none of the prime divisors of $x$ is less than $p$, then $f(xp)=x(p-1)$.

Lemma 1: Let $r$ be a positive integer. Then there exist positive integers $x_1>x_2>\cdots >x_r$ such that $f(x_1)=f(x_2)=\cdots =f(x_r)$

and $x_r$ is prime.

Proof: We will prove the claim by induction on $r$. The case $r=1$ is trivial. Assume that the claim is true for $r\ge 1$. Thus, there exist such $x_1,\dots ,x_r$. For $i=1,\dots ,r$ let $p_i$ be the smallest prime divisor of $x_i$ and $x_i=p_i{y}_i$. Then by Observation 1 we have $$y_1(p_1-1)=y_2(p_2-1)=\cdots =y_{r-1}(p_{r-1}-1)=p_r-1$$ and $p_1<p_2<\cdots <p_r$. Let $A$ be the product of all prime numbers less than $p_r$. Therefore, we have $\gcd (A(p_r-1),p_r)=1$ and thus, by Dirichlet's theorem there exists a prime number $q>p_r$ of the form $A(p_r-1)x+p_r$. Then, $q-1=A(p_r-1)x+p_r-1=(p_r-1)(Ax+1)$. Note that $B=Ax+1$ has no prime divisor less than $p_r$. Thus, we get $B=Ax+1$ for each $i=1,\dots ,r$ and hence, $B{x}_1>B{x}_2>\cdots >B{x}_r>q$ satisfy the conditions for $r+1$.

Lemma 2: Let $q_1<q_2<\cdots <q_k$ be prime numbers and $m={\prod }_{i=1}^k{q}_i^{{\alpha }_i}$. If $f(n)=m$, then $n=2m$ or $n=m+1$ is a prime number or there exists a $1\le j\le k-1$ such that $1+{\prod }_{i=1}^j{q}_i^{{\alpha }_i}$ is a prime number less than $q_{j+1}$ and it is the smallest prime divisor of $n$.

Proof: Let $p$ be the smallest prime divisor of $n$ and $n=px$. Then $x(p-1)={\prod }_{i=1}^k{q}_i^{{\alpha }_i}$. If $x=1$, then $p-1=m$ and $n=p=m+1$ is a prime number. If $p=2$, then $x=m$ and $n=2m$. Now, let $p>2$ and $x>1$. By the observations above we see that $x$ and $p-1$ are relatively prime. Therefore, for every $i=1,\dots ,k$ $q_i^{{\alpha }_i}$ divides exactly one of $x$ and $p-1$. Moreover, if $q_s|p-1$, then $p>q_s$ and none of $q_1,\dots ,q_s$ divides $x$. So, for the largest $j$ satisfying $q_j|p-1$ (there exists such $j$ and $j\ne k$)) we obtain $p-1={\prod }_{i=1}^j{q}_i^{{\alpha }_i}$ and $q_{j+1}<p$.

By Lemma 1 there exists a positive integer $m={\prod }_{i=1}^k{q}_i^{{\alpha }_i}$ with $q_1<q_2<\cdots <q_k$ such that $f(n)=m$ has exactly $r\ge 2023$ solutions. Then by Lemma 2 we see that

$$f(n)=m/q_k^{{\alpha }_k}=\prod _{i=1}^{k-1}{q}_i^{{\alpha }_i}$$ has either r or r - 1 solutions. Indeed, if m + 1 is prime then the number of solutions decreases by 1, otherwise it remains the same. Consequently, we reach a number m' where f(n) = m' has exactly 2023 solutions.