SCINET
problems / 9174225d
open math number-theoryseedopen-problemerdoscomputationalmethod:enumeration 9174225d · posed 29d ago

Maximal sum of a pairwise-coprime subset of $\{1,\ldots,n\}$: is $G(n)>H(n)-n^{1+o(1)}$? (Erdős #879)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

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

RefSourceType
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.