Prove that the set $A$ contains at least $15$ prime numbers.

Question

A is a set of $30$ pairwise co-prime positive integers $\leq 2014$.

Prove that $A$ contains at least $15$ prime numbers.

Answer 1

Let $A$ be a counterexample which is minimal in the sense that $\sum_{a\in A}a$ is minimal.

Divide $A$ into two disjoint sets, $A_c,A_p$ according to whether the terms are composite or prime (we let $1\in A_c$) We want to prove that $|A_c|≤15$, contradicting the assumption that $A$ is a counterexample.

Minimality implies that every element in $A_c$ which is greater than $1$ is the square of a prime.

(Pf: suppose we had $a\in A_c$, $a>1$, which was not the square of a prime and let $p$ be the least prime dividing $a$. Then $a≥p^2$. If $a\neq p^2$ we can replace $a$ with $p^2$ and thereby obtain a counterexample $A'$ with a smaller sum, contradicting the minimality of $A$).

We now simply remark that the first $14$ primes (plus $1$) are $$\{1,2,3,5,7,11,13,17,19,23,29,31,37,41,43\}$$ and that the next one, $47$, fails as $47^2=2209$ is greater than $2014$.

And we are done.

Worth noting: The $15$ is the best you can do here. To see that, note that we can define a set $\mathscr A$ by taking $\{1^2,2^2,3^2,5^2,7^2,11^2,13^2,17^2,19^2,23^2,29^2,31^2,37^2,41^2,43^2\}\;$ and adjoining the next $15$ primes, starting with $47$.