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

Divergence of $\sum 1/a_i$ for the Eggleton–Erdős–Selfridge coprime sequence (Erdős #460)

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

Statement

Fix a positive integer $n$. Define a sequence by $a_0=0$, $a_1=1$, and for $k\geq 2$ let $a_k$ be the least integer $>a_{k-1}$ such that $\gcd(n-a_k,\,n-a_i)=1$ for all $0\leq i<k$. Does $$\sum_{0<a_i<n}\frac{1}{a_i}\to\infty\quad\text{as }n\to\infty\,?$$ The same question is asked for the sum restricted to those $i$ for which $n-a_i$ is divisible by some prime $\leq a_i$, and for the sum over the complementary set of $i$. (The restriction $a_i<n$ in the sum is essential: without it the sum is infinite, since the sequence contains $n+p$ for every prime $p>n$.)

Acceptance. FULLY RESOLVES (proof-shaped): a complete proof — machine-checkable (Lean/Coq) preferred, else fully written — settling whether $\sum_{0<a_i<n}1/a_i\to\infty$ for the main formulation above (and, for full credit, the two restricted variants). ADVANCES: a proof that Chojecki's sufficient condition $f(n)\to\infty$ holds; a proof of the conjectured growth $a_k\ll k\log k$, strictly improving the recorded $a_k<k^{2+o(1)}$ bound; or a reproducible computation of $a_k$ and of the partial sums $\sum_{0<a_i<n}1/a_i$ over a substantially extended range of $n$ and $k$, with the program and certified data, that supports or rules out divergence. Deliver the proof, or the computation code plus tabulated growth data.

Background

This question arose in work of Eggleton, Erdős and Selfridge [Er77c, p.64], reiterated in Erdős–Graham [ErGr80, p.91]; listed as open on erdosproblems.com/460 (fetched 2026-07-21, status 'open'). They proved $a_k<k^{2+o(1)}$ (for $k$ large depending on $n$) and conjectured the much stronger $a_k\ll k\log k$. The two sources state the problem slightly differently (one takes $a_0=n$ and ranges over $1\leq i<k$), and Bloom notes the precise intended formulation and its motivation are unclear because the promised Eggleton–Erdős–Selfridge paper cannot be located. Chojecki observed (site comments) that a positive answer to the main question would follow from $f(n)=\sum_{a<n,\,P^-(n-a)>a}1/a\to\infty$, where $P^-$ denotes least prime factor; standard rough-number estimates give $\frac{1}{N}\sum_{n\leq N}f(n)\gg\log\log N$, so $f(n)\to\infty$ on average, but pointwise divergence is open. No prize. Attacker's tool: direct computation of the greedy sequence $\{a_k\}$ and its partial reciprocal sums for many $n$ (probing divergence and the $a_k\ll k\log k$ growth conjecture), plus analytic estimates on the distribution of least prime factors to control $f(n)$.

References

RefSourceType
REF-01 Erdős Problem #460 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.