What is the maximum number of integers we can choose from the set $\{1,2,3, \ldots, 2017\}$ such that the difference between any two of them is not a prime number?
Solution

The largest quantity is $\frac{2017-1}{4}+1=505$, which can be obtained by choosing the elements that leave a remainder of 1 when divided by 4: $\{1,5,9, \ldots, 2017\}$. The difference between any two of them is always a multiple of 4 and consequently is not a prime number. We will now show that it is not possible to choose more than this quantity.

Consider the 8 consecutive positive integers $\{n, n+1, n+2, n+3, n+4, n+5, n+6, n+7\}$. We want to study how many integers can be chosen from this set so that the difference between any two of them is a prime number.

i) If the integer $n$ is chosen, we cannot choose $n+2, n+3, n+5$ and $n+7$, because the difference between them and $n$ is a prime number. Moreover, $n+1$ and $n+6$ cannot be chosen simultaneously, as they differ by 5. Thus, if we choose $n$, we can choose only two integers from the set.

ii) Suppose then that $n$ is not chosen. If we choose $n+1$, we cannot choose $n+3, n+4, n+6$. Furthermore, from the remaining set $\{n+2, n+5, n+7\}$ only one of them can be chosen. Again, we can choose only two integers from the set.

iii) Suppose now that $n$ and $n+1$ are not chosen. If we choose $n+2$, we cannot choose $n+4, n+5$ and $n+7$. Moreover, from the remaining set $\{n+3, n+6\}$ only one of them can be chosen. Again, the maximum number is two.

iv) If $n, n+1$ and $n+2$ are not chosen, but $n+3$ is, we cannot choose $n+5$ and $n+6$. From the set $\{n+4, n+7\}$ only one of them can be chosen. The maximum number of integers that can be chosen is also two in this case.

v) Considering the pairs $(n+4, n+6)$ and $(n+5, n+7)$, only one integer from each pair can be chosen. Therefore, if the first four in the list are not chosen, we can choose at most two.

Dividing the numbers from 1 to 2016 into 2016/8 = 252 groups of 8 consecutive integers, we can conclude that in each of them we can choose at most 2 integers. Thus, counting with 2017, we will have at most $2 \cdot 252+1=505$ integers that can be chosen satisfying the conditions of the statement.

#