Erdoes #879 - working report - Erdős Problem a Day

Erdős problem #879 — wave w020

Accessed and computed on 2026-07-28. Claim labels used below are:

(a) elementary-rigorous: proved here from definitions or directly checked

page metadata;

(b) rigorous-modulo-named-theorem: dependent on the cited theorem/source;
(c) plausible/structural-unverified: a heuristic or conjectural direction;
(d) computational-only: exact finite computation, not an asymptotic

theorem.

0. Mandatory live-page check

(a, direct page observation.) I fetched the live page, its LaTeX view, and its discussion thread through the Bright Data browser path. The live page said OPEN, `0 claimed proofs for this problem, and Currently working on this problem: None`. It also showed Interested in collaborating: None, and all of the “looks difficult,” “looks tractable,” formalisation-interest, and like markers as None. Thus the stop condition was not triggered. The page had one comment, discussed below.

Verbatim current 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?

(a, interpretation used here.) The maximum in the displayed definition is understood to range over the admissible sets just defined. For the second question I use distinct prime factors, which is the interpretation made in the live comment via $\omega(\operatorname{rad}m)$.

Known results listed live

(b, Erdős–van Lint as reported live and checked in the original scan.) The page lists

H(n)-n^{3/2-o(1)}<G(n)<H(n),\qquad \frac{H(n)-G(n)}n\longrightarrow\infty.

It says that the $n^{1+o(1)}$ lower bound follows under “plausible (but hopeless) assumptions about the distribution of primes,” and that the second question is proved for $k=2$. It points to problem #878 and OEIS A186736.

(a, bibliographic check; b for the quoted mathematical results.) Page 120 of Erdős, “On two unconventional number theoretic functions and on some related problems”, Calcutta Mathematical Society Diamond-cum-Platinum Jubilee Commemoration Volume, Part I (1984), 113–121, really contains the definition, asymptotic, two-sided bound, divergent normalized gap, the conditional $n^{1+\varepsilon}$ bound, and the question about more than $r$ prime factors. The scan uses $a_i<n$, whereas the authoritative live page uses $\{1,\ldots,n\}$; all computations here follow the live $\le n$ convention.

(a, bibliographic only.) The second listed reference really exists: P. Erdős, “Some of my new and almost new problems and results in combinatorial number theory”, in Number Theory (Eger, 1996), De Gruyter (1998), 169–180, MR 1628841. Publisher metadata was available, but the chapter text was paywalled, so I assign no independent mathematical claim to it.

(a, honest literature-search result.) Searches by the exact title, the phrases “$H(n)-G(n)$” and “relatively simple algorithm for computing $G(n)$,” and the pairwise-coprime maximum-sum formulation found no later primary paper that I could verify as improving this problem. A recent search hit, Eric Li’s arXiv:2606.17955, studies the different shifted reciprocal functional $\sup_A\sum_{a\in A}1/(n-a)$, not the present maximum-sum functional. This is a search miss report, not a proof that no relevant literature exists.

The one live comment

(a, direct page observation.) Zeraoulia Rafik’s comment of 2026-05-26 gives the radical integer program, defines $G_{\le2}(n)$, and reports $G(n)=G_{\le2}(n)$ at

\[ 20,50,100,200,500,1000,2000,5000,10000,20000. \]

It explicitly labels the experiment finite evidence and suggests, only as a counter-conjecture, that equality might hold infinitely often or always.

(a for the mandatory $+1$; d for the independently optimized values.) Every objective value in that comment is one too small under the live definition. The comment says that the unconstrained radical $1$ is always selected, but its table omits its weight. For example,

\{1,7,11,13,15,16,17,19\}

is admissible in $[1,20]$ and sums to $99$, while the comment prints $98$. The independently recomputed values are exactly the displayed values plus $1$. The comment’s equality $G=G_{\le2}$ survives this correction at its listed sample points.

1. Exact reduction

For a prime $p\le n$, define its best singleton

P_n(p)=\max\{p^a:p^a\le n,\ a\ge1\}.

For a finite set $R$ of primes whose squarefree product is at most $n$, define

w_n(R)=\max\{m\le n:\{p:p\mid m\}=R\}

and, when $|R|\ge2$,

\Delta_n(R)=w_n(R)-\sum_{p\in R}P_n(p).

Let a matching of prime supports mean a family $\mathcal M$ of pairwise disjoint such sets $R$.

Lemma (a, elementary-rigorous).

\boxed{\quad G(n)=1+\sum_{p\le n}P_n(p) +\max_{\mathcal M}\sum_{R\in\mathcal M}\Delta_n(R). \quad} \tag{1}

The maximum may discard every support with $\Delta_n(R)\le0$. Moreover,

G_{\le2}(n)=1+\sum_{p\le n}P_n(p) +\max_{\substack{\mathcal M\\ |R|=2}} \sum_{R\in\mathcal M}\Delta_n(R). \tag{2}

Thus (2) is an ordinary maximum-weight graph matching problem, whereas (1) is a weighted hypergraph matching/set-packing problem.

Proof (a). Add $1$, which conflicts with nothing and has positive weight. Replace every other selected integer $m$ by $w_n(R)$, where $R$ is its distinct-prime support. This preserves pairwise coprimality and does not decrease the sum. The selected supports are pairwise disjoint. Every prime not used in a multi-prime support can then be represented by $P_n(p)$; omitting it would leave a positive admissible summand unused. Starting with all these singleton prime powers and replacing the singletons on $R$ by $w_n(R)$ changes the objective by exactly $\Delta_n(R)$. Summing over disjoint $R$ proves (1). Restricting to at most two distinct prime factors leaves only the two-element supports and proves (2). $\square$

(a.) This is a reduced form of the live comment’s integer program: nonpositive-gain supports can be deleted before optimization because they can never improve the value.

2. Exact finite computation

Method (d). The standalone checker erdos879_wavew020_verify.py (SHA-256 ca9087aedd966d66e5b73846eaf866424785db0b52e7a6923207515455ec16b1) does all of the following from scratch.

It sieves least prime factors, radicals, distinct-prime supports, $w_n$,

and $P_n$.

It builds only positive $\Delta_n$ edges and solves both (1) and (2) as

integer models. It accepts a result only when single-worker OR-Tools CP-SAT returns OPTIMAL with objective equal to its best bound.

It reconstructs the actual admissible set, checks disjoint prime supports,

its range, distinctness, and its sum.

Independently for every $n\le30$, it performs a direct dynamic program

over every radical support, without using (1) or CP-SAT.

It checks the corrected numerical values as assertions rather than using

them as optimizer input.

The tested environment was Python 3.12.3 and OR-Tools 9.15.6755. Run:

python runs/erdos879_wavew020_verify.py

The full default audit completed successfully in about 109 wall-seconds on this VM. The direct-DP values and CP-SAT values agree through $30$.

Results

(d, exact finite computation.)

\boxed{G(n)=G_{\le2}(n)\quad\text{for every }1\le n\le5000.} \tag{3}

Consequently, for each $n$ in this finite interval there exists an optimal admissible set containing no integer with three distinct prime factors. This does not say that every optimum has that property.

(d.) The first positive-gain support with three primes already occurs at $n=110$:

R=\{2,5,11\},\qquad \Delta_{110}(R)=110-(64+25+11)=10.

Thus (3) is not an artifact of all higher-order supports being individually worthless: graph matchings elsewhere still absorb their potential gain.

The corrected exact table is:

| $n$ | $G(n)$ | $G_{\le2}(n)$ | $H(n)-G(n)$ | positive $\omega\ge3$ supports | |---:|---:|---:|---:|---:| | 20 | 99 | 99 | 18 | 0 | | 50 | 446 | 446 | 82 | 0 | | 100 | 1,356 | 1,356 | 104 | 0 | | 200 | 5,105 | 5,105 | 322 | 0 | | 500 | 24,915 | 24,915 | 621 | 6 | | 1,000 | 85,685 | 85,685 | 1,442 | 6 | | 2,000 | 302,546 | 302,546 | 2,504 | 68 | | 5,000 | 1,636,901 | 1,636,901 | 6,235 | 29 | | 10,000 | 5,972,790 | 5,972,790 | 13,606 | 195 | | 20,000 | 21,825,995 | 21,825,995 | 25,196 | 92 | | 50,000 | 123,340,388 | 123,340,388 | 72,920 | 2,500 | | 100,000 | 460,762,887 | 460,762,887 | 133,650 | 4,072 | | 200,000 | 1,726,545,007 | 1,726,545,007 | 255,806 | 5,359 | | 500,000 | 9,976,565,608 | 9,976,565,608 | 670,587 | 33,993 |

(d.) Equality in the rows above $5000$ is at the displayed sample points only, not throughout the intervening intervals. CP-SAT proved both objectives optimal at each sample. The increasing number of positive higher-order supports makes the equality nontrivial, but no finite table can decide either eventual question.

3. A clean sufficient reduction for the first question

Let $\mathcal P=\{p:p\le\sqrt n,\ p\text{ prime}\}$. Suppose there is a subset $\mathcal P'\subseteq\mathcal P$, with

|\mathcal P\setminus\mathcal P'|=n^{o(1)},

and an injection

p\longmapsto q_p

from $\mathcal P'$ to distinct primes $q_p>\sqrt n$, with $p q_p\le n$, such that

D(n):=\sum_{p\in\mathcal P'}(n-pq_p)\le n^{1+o(1)}. \tag{4}

Proposition (b, rigorous modulo the standard Mertens bound $\sum_{p\le x}1/p=O(\log\log x)$). Condition (4) implies

G(n)>H(n)-n^{1+o(1)}.

Proof. Start with all primes below $n$. For every $p\in\mathcal P'$, replace $p$ and $q_p$ by $pq_p$. The injection and the separation $p\le\sqrt n<q_p$ make the resulting set pairwise coprime. Include $1$. The deficit from $H(n)$ is

\sum_{p\in\mathcal P'}\bigl(n-pq_p+p+q_p\bigr) +n|\mathcal P\setminus\mathcal P'|-1.

The first part $\sum(n-pq_p)$ is (4); $\sum_{p\in\mathcal P'}p\le n$; and

\sum_{p\in\mathcal P'}q_p\le n\sum_{p\le\sqrt n}\frac1p =O(n\log\log n)=n^{1+o(1)}.

The exceptional primes cost $n|\mathcal P\setminus\mathcal P'|=n^{1+o(1)}$. Thus the whole deficit is at most $n^{1+o(1)}$; enlarging the representative error function within the same $n^{1+o(1)}$ class makes the displayed inequality strict. This gives the claimed admissible construction. $\square$

This isolates a concrete missing analytic-combinatorial lemma: a simultaneous prime matching near the moving endpoints $n/p$, with total weighted shortfall $n^{1+o(1)}$. Individual prime-gap statements are not by themselves enough unless they also provide the required injectivity/Hall condition across all but $n^{o(1)}$ of the primes $p\le\sqrt n$.

4. What remains and why this does not close the problem

(a, exact logical diagnosis.) For the second question at a fixed $k$, the strict inequality

G(n)>G_{\le k-1}(n)

is equivalent to every optimum having to use at least $k$ distinct prime factors. Formula (1) turns that version into a uniform strict separation between weighted hypergraph matchings of ranks $k$ and $k-1$. If the question instead asks only for the existence of one such optimum, strict separation is stronger than necessary and one must also analyze zero-loss alternative exchanges. The finite result (3) goes in the opposite direction for $k=3$, but it has no force on an eventual quantifier.

(c.) The live commenter’s conjecture that $G=G_{\le2}$ infinitely often or always remains only a conjecture. The computations here neither support a uniform proof mechanism nor find a counterexample.

(d, costed computation wall.) The all-$n$ checker rebuilds a prefix hypergraph and empirically has roughly quadratic prefix cost. From the measured 85 seconds through $5000$, a naive scan through $20{,}000$ would cost roughly $0.4$ core-hour before harder-instance overhead (budget $0.5$–$2$ core-hours). A naive scan through $500{,}000$ would be about $2.4\times10^2$ core-hours by quadratic extrapolation, plausibly $250$–$1000$ core-hours after solver overhead (roughly \$10–\$80 at \$0.04–\$0.08/core-hour). Such a scan is embarrassingly parallel but still cannot prove an eventual claim. The useful missing theorem is the uniform prime-matching lemma (4) for question 1, or a uniform rank-separation/replacement lemma for (1) for question 2—not a larger isolated table.

PARTIAL: Corrected the live comment's off-by-one error, proved the exact baseline-plus-hypermatching reduction, and computationally verified $G(n)=G_{\le2}(n)$ for every $n\le5000$ plus exact samples through $500000$; the asymptotic prime-matching/rank-separation lemma remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger