Problem 879

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?

Source: erdosproblems.com/879

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open. The site's label is OPEN. Two pending partial claims bear on the second question: Erdős's statement of 1984, which the site credits to Erdős and van Lint, that it holds at $k=2$ (claim page (Erdős and van Lint, 1984)), and Kenta Kitamura's Lean development of September 2026, made with OpenAI Codex and ChatGPT Astra, which answers it no at $k=3$ (claim page (Kitamura, 2026)). The first question is open; the results bearing on it are under Progress. The standing in the frontmatter is derived from the claim pages.

Problem 879

Status

Proof claims

Discussion