Let $A$ be a subset of $\{1,2,3, \ldots, 2019\}$ having the property that the difference between any two of its elements is not a prime number. What is the largest possible number of elements of $A$? 

#
Solution

Suppose $a \in A$. Then, no element of the set $\{a+2, a+3, a+5, a+7\}$ can belong to $A$, and among the elements of $\{a+1, a+4, a+6\}$, at most one of them can belong to $A$. Thus, in every 8 consecutive integers, say the elements of the set $\{a, a+1, a+2, \ldots, a+7\}$, at most two of them can belong to $A$. Therefore, the maximum number of elements in $A$ is not greater than the largest integer that does not exceed 2019/4 plus 1, which is 505. This quantity can be achieved with the set $\{3,7,11, \ldots, 2019\}$. Note that the difference between any two of them is a multiple of $4$ and, consequently, cannot be a prime number. Therefore, the maximum number of elements is 505.