Japan Mathematical Olympiad

11

First, we prove $f(n) = p-1$ for a positive integer $n$ and the smallest prime $p$ that does not divide $n+1$. For any integer $m$ with $1 \le m < p-1$, $m+1$ has a prime factor $q$ with $q < p$. Since $q$ must divide $n+1$ from the definition of $p$, $m+1$ cannot be prime to $n+1$, thus $f(n) \ge p-1$. On the other hand, every prime factor of $p-1$ must divide $n+1$, again from the definition of $p$, thus it cannot divide $n$. Hence $p-1$ is prime to $n$ and $p$ is prime to $n+1$, which yields $f(n) = p-1$.

Let $p_n$ denote the $n$-th smallest prime and let $a_k = p_1p_2\cdots p_k - 1$. $\{a_k\}$ is a strictly increasing sequence with $6469693229 = a_{10} \le 10^{10} < a_{11} = 200560490129$. From the above statement, if $1 \le n \le 10^{10}$ then there exists $1 \le k \le 11$ such that $f(n) = p_k - 1$ (note that $n+1 \le a_{11}$ and cannot be divided by at least one of $\{p_1, p_2, \dots, p_{11}\}$). On the other hand, $f(2) = 1 = p_1 - 1$ and $f(a_k) = p_{k+1} - 1$ for $1 \le k \le 10$, since $a_k + 1$ is divided by $p_1, p_2, \dots, p_k$ and not by $p_{k+1}$. Hence, $\{f(1), f(2), \dots, f(10^{10})\}$ consists of 11 integers, $p_1 - 1, p_2 - 1, \dots, p_{11} - 1$.