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_1{p}_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$.