Maximal sum of a pairwise-coprime subset of $\{1,\ldots,n\}$: is $G(n)>H(n)-n^{1+o(1)}$? (Erdős #879)
Statement
Call a set $S\subseteq\{1,\ldots,n\}$ admissible if its elements are pairwise coprime, i.e. $(a,b)=1$ for all distinct $a,b\in S$. Let $$G(n)=\max_{\substack{S\subseteq\{1,\ldots,n\}\\ S\text{ admissible}}}\ \sum_{a\in S}a$$ be the largest possible sum of a pairwise-coprime subset, and set $$H(n)=\sum_{p<n}p\ +\ n\,\pi(n^{1/2}),$$ where the sum runs over primes $p<n$ and $\pi$ is the prime-counting function. Two questions are asked. (1) Is it true that $$G(n)>H(n)-n^{1+o(1)}?$$ (2) Is it true that for every $k\geq 2$, once $n$ is sufficiently large, every admissible set attaining the maximum $G(n)$ contains at least one integer having at least $k$ prime factors?
Acceptance. FULLY RESOLVES (proof-shaped): a complete written or machine-checkable proof of (1) that $G(n)>H(n)-n^{1+o(1)}$ holds unconditionally — i.e. without the prime-distribution hypotheses used by Erdős–van Lint — or a disproof; or a complete proof of (2), that for every fixed $k\geq 2$ and all large $n$ every maximiser of $G(n)$ contains an integer with at least $k$ prime factors, or a counterexample for some $k$. ADVANCES (checkable): improve the lower estimate from the recorded $G(n)>H(n)-n^{3/2-o(1)}$ to $G(n)>H(n)-n^{\theta+o(1)}$ for an explicit $\theta<3/2$, with proof; establish (2) for a specific new value $k\geq 3$, with proof; or a certified exact computation of $G(n)$ and its optimal admissible sets over a documented range extending OEIS A186736, reporting the largest number of prime factors forced in an optimum as a function of $n$. Deliver the proof/formalisation or the reproducible computation with certified $G(n)$ values.
Background
Posed by Erdős [Er84e] (see also [Er98]); listed as open on erdosproblems.com/879 (fetched 2026-07-21, status 'open'), OEIS A186736. Erdős and van Lint proved the two-sided estimate $$H(n)-n^{3/2-o(1)}<G(n)<H(n)$$ together with $\big(H(n)-G(n)\big)/n\to\infty$, so $G(n)$ sits just below $H(n)$ but the gap is superlinear in $n$; question (1) asks to shrink the lower estimate's error term from $n^{3/2-o(1)}$ down to $n^{1+o(1)}$. They could prove $G(n)>H(n)-n^{1+o(1)}$ only under (in their words) plausible but hopeless assumptions about the distribution of primes. For question (2) they settled the case $k=2$. The companion problem is Erdős #878 (erdosproblems.com/878). An attacker would compute $G(n)$ exactly for $n$ in a large range — a maximum-weight selection of pairwise-coprime integers, extending OEIS A186736 — study the structure of the optimal admissible sets to test claim (2), and bring analytic prime-distribution estimates to tighten the error term toward $n^{1+o(1)}$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #879 (T. F. Bloom) | website |
| REF-02 | OEIS A186736 | website |
| REF-03 | Erdős Problem #878 (companion; T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.