MathDB

4. Call a subset

S

of the set

\{1,\dots,n\}

exceptional if any pair of distinct elements of

S

are coprime. Consider an exceptional set with a maximal sum of elements (among all exceptional sets for a fixed

n

). Prove that if

n

is sufficiently large, then each element of

S

has at most two distinct prime divisors. (N.17) [P. Erdos]

Problem Statement