Does the odd-greedy Egyptian-fraction algorithm always terminate for odd-denominator rationals? (Erdős #282)
Statement
Given an infinite set $A\subseteq\mathbb{N}$, run the following greedy algorithm on a rational $x\in(0,1)$: pick the minimal $n\in A$ with $n\geq 1/x$, replace $x$ by $x-\frac1n$, and repeat. If the process halts after finitely many steps it writes $x$ as a sum of distinct unit fractions with denominators drawn from $A$. When $A$ is the set of odd positive integers and $x$ has odd denominator, does this process always terminate? More generally, for which pairs $(x,A)$ does the greedy process terminate?
Acceptance. FULLY RESOLVES (proof-shaped): a complete proof that the odd-greedy algorithm terminates for every rational with odd denominator (Stein's question), or an explicit odd-denominator rational $x$ for which it provably never terminates (a finite certificate exhibiting the non-halting structure together with a proof of non-termination). The universal statement requires a rigorous proof — machine-checkable preferred, otherwise a full written proof; simulation alone cannot certify 'always terminates'. ADVANCES (each independently checkable): (a) verify termination by simulation for all odd-denominator rationals $m/n$ up to a stated height bound, with reproducible code and the attained bound, strictly beyond any previously reported range; (b) settle the greedy-termination question for another of Graham's denominator families (an arithmetic progression, or square denominators) — e.g. exhibit an explicit non-terminating $x$ for square denominators; (c) prove termination for a structured subclass of odd-denominator $x$. Deliver the proof/witness, or the simulation code plus the attained verified bound.
Background
Fibonacci (1202) showed that for $A=\mathbb{N}$ the greedy process terminates for every $x\in(0,1)$ (the Fibonacci–Sylvester expansion). The odd-denominator version is due to Stein and is posed by Erdős and Graham [ErGr80, p.30]. Graham [Gr64b] characterised which $m/n$ are sums of distinct unit fractions with denominators $\equiv a\pmod d$ — this holds iff $\left(\frac{n}{(n,(a,d))},\frac{d}{(a,d)}\right)=1$ — and [Gr64c] showed $x$ is a sum of distinct unit fractions with square denominators iff $x\in[0,\pi^2/6-1)\cup[1,\pi^2/6)$; but whether the corresponding greedy algorithm terminates is open, and Erdős and Graham expect the square-denominator greedy algorithm to fail to terminate almost always. See also erdosproblems.com/206. There is no Erdős prize attached. Listed as open on erdosproblems.com/282 (fetched 2026-07-21, status 'open'). Attacker's tool: directly simulate the odd-greedy expansion on all odd-denominator rationals up to a large height, extending the range over which termination is verified and hunting for a non-terminating instance; for the square-denominator variant, search for an explicit non-halting $x$, which would be a concrete falsifying witness.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #282 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.