Problem Statement
Call a set $S\subseteq \{1,\ldots,n\}$ admissible if $(a,b)=1$ for all $a\neq b\in S$. Let\[G(n) = \max_{S\subseteq \{1,\ldots,n\}} \sum_{a\in S}a\]and\[H(n)=\sum_{p<n}p+ n\pi(n^{1/2}).\]Is it true that\[G(n) >H(n)-n^{1+o(1)}?\]Is it true that, for every $k\geq 2$, if $n$ is sufficiently large then the admissible set which maximises $G(n)$ contains at least one integer with at least $k$ prime factors?
Categories:
Number Theory
Progress
Erdős and Van Lint proved that\[H(n)-n^{3/2-o(1)}<G(n)<H(n)\]and\[\frac{H(n)-G(n)}{n}\to \infty.\]They proved that $G(n)>H(n)-n^{1+o(1)}$ assuming 'plausible (but hopeless) assumptions about the distribution of primes'. They also prove the second claim when $k=2$.See also [878].
Source: erdosproblems.com/879 | Last verified: January 19, 2026