Erdős Problem #282

Round 2 continuation for Erdős Problems #282, #283, #287

Erdős Problem #282

1) ROUND-2 OBJECTIVE

I pursue (C) obstruction/correction for the broad "for which pairs $(x,A)$ does the greedy process terminate?" part of the problem. Round 1 left the Stein case $(A=$ all odd numbers$,\ x$ of odd denominator$)$ unresolved, but it did not yet separate that case from the behaviour of sparse allowed sets. The most promising Round-2 target is therefore to produce an explicit infinite family of rational pairs $(x,A)$ for which the greedy process provably does not terminate, and to sharpen the arithmetic obstruction for finite odd expansions.

2) Round-1 FOUNDATION USED

I use the following Round-1 items without reproving them.

1. The corrected distinct-denominator greedy algorithm: at each step choose the least unused $n\in A$ with $1/n\le x$.
2. The basic odd-denominator obstruction: if a finite sum of distinct odd unit fractions equals $a/b$ in lowest terms, then $b$ is odd.
3. The classical Fibonacci--Sylvester termination proof for $A$ equal to the full set of positive integers.
4. The Round-1 computational fact that the odd greedy algorithm terminated for all reduced $a/b\in(0,1)$ with odd $b\le 51$.

3) NEW INSIGHT / TOOL (ROUND-2)

There are two genuinely new ingredients in this round.

1. A Sylvester-tail nontermination family: for every integer $m\ge 3$ there is an explicit infinite set $A_m$ and a rational $x_m=1/(m-1)$ such that the restricted greedy algorithm on $(x_m,A_m)$ follows a closed-form infinite trajectory and never terminates.
2. A mod $8$ terminal invariant for odd expansions: if \[ \frac{a}{b}=\frac1{n_1}+\cdots+\frac1{n_t} \] with all $n_i$ odd and $a/b$ in lowest terms, then \[ n_1+\cdots+n_t\equiv a b^{-1}\pmod 8, \] where $b^{-1}$ is the inverse of $b$ modulo $8$.

The first result shows that rational nontermination is abundant for sparse allowed sets, even inside odd sets and even inside a single residue class. The second result strengthens the Round-1 parity obstruction.

4) ATTACK PLAN (ROUND-2)

Round 1 identified the main gap as the absence of either a global monotone quantity or an explicit nonterminating trajectory. I therefore prove the following two precise claims.

1. For each $m\ge 3$, the pair \[ x_m=\frac1{m-1},\qquad A_m=\{a_1,a_2,a_3,\dots\} \] with \[ a_1=m,\qquad a_{r+1}=(m-1)a_1a_2\cdots a_r+1 \] produces an infinite greedy expansion.
2. Any finite odd Egyptian expansion satisfies a stronger congruence modulo $8$.

These claims do not settle the Stein case, but they overcome two specific Round-1 obstacles: they exhibit explicit nontermination for rational input, and they sharpen the arithmetic constraints on any hypothetical terminal odd expansion.

5) WORK (ROUND-2)

5.1. An explicit infinite nonterminating family.

Fix an integer $m\ge 3$. Define \[ a_1=m,\qquad a_{r+1}=(m-1)a_1a_2\cdots a_r+1\quad (r\ge 1), \] and let \[ A_m:=\{a_1,a_2,a_3,\dots\},\qquad x_m:=\frac1{m-1}. \] Let \[ P_r:=a_1a_2\cdots a_r. \] I claim that the greedy algorithm for $(x_m,A_m)$ chooses $a_1,a_2,\dots$ in order and has remainder \[ R_r:=x_m-\sum_{j=1}^r \frac1{a_j}=\frac1{(m-1)P_r}\qquad (r\ge 0), \] where by convention $P_0=1$.

For $r=0$ this is exactly $R_0=x_m=1/(m-1)$. Assume the formula holds for some $r\ge 0$. Then \[ \frac1{R_r}=(m-1)P_r, \] so by definition of the sequence, \[ a_{r+1}=\frac1{R_r}+1. \] Hence \[ R_r-\frac1{a_{r+1}} =\frac1{(m-1)P_r}-\frac1{(m-1)P_r+1} =\frac1{(m-1)P_r\left((m-1)P_r+1\right)} =\frac1{(m-1)P_{r+1}}. \] Thus the remainder formula holds for all $r$ by induction.

It remains to check the greedy choice. Since $a_{r+1}=1/R_r+1$, we have $a_{r+1}>1/R_r$, so $1/a_{r+1}<R_r$. Also $a_1<a_2<a_3<\cdots$, because \[ a_{r+1}=(m-1)P_r+1>(m-1)a_r+1>a_r. \] Therefore every previously used denominator is $<a_{r+1}$, and every unused element of $A_m$ is at least $a_{r+1}$. So among unused elements of $A_m$, the least one satisfying $1/n\le R_r$ is exactly $a_{r+1}$. This is precisely the corrected greedy rule.

Since $R_r=1/((m-1)P_r)>0$ for every $r$, the algorithm never reaches $0$. Therefore \[ \frac1{m-1}=\sum_{r=1}^{\infty}\frac1{a_r} \] is an infinite greedy expansion and the greedy process does not terminate.

5.2. Two useful corollaries of the family.

1. If $m$ is odd, then every $a_r$ is odd. Indeed $a_1=m$ is odd, and if $a_1,\dots,a_r$ are odd then $(m-1)P_r$ is even, so $a_{r+1}=(m-1)P_r+1$ is odd. Thus for every odd $m\ge 3$ we obtain an explicit nonterminating rational pair with $A_m$ contained in the odd positive integers.
2. If $m\equiv 1\pmod d$, then every $a_r\equiv 1\pmod d$. This is immediate from \[ a_{r+1}=(m-1)P_r+1\equiv 1\pmod d. \] Hence for every modulus $d\ge 1$ there are nonterminating rational pairs $(x,A)$ with $A$ contained in a single residue class modulo $d$.

These corollaries do not settle the open odd/full-set question, because the first family has $x_m=1/(m-1)$ and therefore even denominator when $A_m$ is odd, and the second family lies outside Graham's admissible congruence condition in the natural example $A\subseteq\{n\equiv 1\pmod d\}$ with $x=1/d$.

5.3. A stronger terminal obstruction for odd expansions.

Suppose \[ \frac{a}{b}=\frac1{n_1}+\cdots+\frac1{n_t} \] with all $n_i$ odd and $a/b$ in lowest terms. Because $b$ is odd, the residue class $b^{-1}\pmod 8$ is defined.

For any odd integer $u$ one has $u^2\equiv 1\pmod 8$, hence $u^{-1}\equiv u\pmod 8$. Therefore, in the ring of rationals with odd denominator modulo $8$, \[ \frac1{n_i}\equiv n_i\pmod 8. \] Summing over $i$ gives \[ \frac{a}{b}=\sum_{i=1}^t \frac1{n_i}\equiv \sum_{i=1}^t n_i\pmod 8. \] Multiplying by $b$ yields the equivalent integer congruence \[ n_1+\cdots+n_t\equiv a b^{-1}\pmod 8. \] This strictly strengthens the Round-1 parity statement: reducing modulo $2$ only recovers the fact that $b$ must be odd, whereas modulo $8$ one gets a definite residue class for the total denominator sum.

6) ADVERSARIAL VERIFICATION

I checked the new work against the main failure modes.

1. Greedy-rule ambiguity. The proof uses the Round-1 corrected greedy rule with distinct denominators. This matters: the sequence $A_m$ is strictly increasing, so the least unused allowed denominator is unambiguous at every step.
2. Could an earlier unused element of $A_m$ be large enough to interfere? No. There are no earlier unused elements: the greedy trajectory uses $a_1,a_2,\dots$ in order, and $A_m$ is strictly increasing.
3. Could the family accidentally solve the Stein case? No. When $A_m$ is odd, $x_m=1/(m-1)$ has even denominator. So this family lies deliberately outside Stein's hypothesis.
4. Could the residue-class corollary refute the admissible congruence-class question? No. For the natural choice $A\subseteq\{n\equiv 1\pmod d\}$ and $x=1/d$, Graham's admissibility condition fails, so these examples do not contradict the open admissible case.
5. Is the mod $8$ congruence really stronger than Round 1? Yes: it gives a specific residue class for the terminal denominator sum, not merely oddness of the reduced denominator.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The Stein problem for the full odd set remains open, but Round 2 makes two substantive advances beyond Round 1.

1. It gives an explicit infinite family of rational nonterminating greedy trajectories, including examples with $A$ odd and examples with $A$ contained in one residue class modulo an arbitrary $d$.
2. It upgrades the odd-denominator terminal obstruction from a parity statement to a sharp congruence modulo $8$.

So the broad "for which pairs $(x,A)$?" question is now sharply separated from the special full-set odd case: sparse allowed sets can force rational nontermination, while the Stein case remains the real unresolved core.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

Checked or used in this round:

1. T. F. Bloom, Erdős Problem #282, webpage accessed 2026-03-07.
2. W. van Doorn, Partitions with prescribed sum of reciprocals: computational results, arXiv:2502.01409 (checked for context; the congruence used above was reproved directly).

Problem 282: exact tests of the distinct odd greedy algorithm

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read the complete 282.tex, including its sparse Sylvester sets, modular invariant, and distinction from the full odd-denominator problem. I investigate its explicitly stated distinct-denominator greedy convention: subtract the reciprocal of the least unused odd integer whose reciprocal does not exceed the positive remainder. Sparse allowed sets do not decide termination for the full odd set.

2) WORK

For a reduced remainder $a/b$ with odd $b$, and a selected odd denominator $n$, the next reduced numerator and denominator are \[ a'=\frac{an-b}{g},\quad b'=\frac{bn}{g},\qquad g=\gcd(an-b,bn). \] Before termination $g$ is odd. Therefore $b'$ remains odd and \[ a'\equiv a-1\pmod2. \] Reduced numerator parity alternates at every nonterminal step. If the distinctness restriction does not force skipping the least eligible odd denominator, then $0\le an-b<2a$. This controls one-step growth but does not imply descent. For instance the trajectory from $2/7$ is \[ \frac27\longmapsto\frac3{35}\longmapsto\frac4{455} \longmapsto\frac1{10465}\longmapsto0, \] using denominators $5,13,115,10465$. Its numerator increases twice before a common factor causes a decrease.

I executed an exact rational search for every reduced $a/b\in(0,1)$ with odd $3\le b\le101$. With previous denominator $\ell$, the next denominator is the least odd integer at least \[ \max\{\ell+2,\lceil b/a\rceil\}. \] This is exactly the least unused eligible denominator: every smaller unused denominator was too small at an earlier, larger remainder and remains ineligible. All 2,106 fractions terminated. The longest run used 18 terms; the largest denominator or intermediate reduced denominator used 11,711 binary digits. No run reached the imposed caps of 200 steps or 100,000 bits. Full denominator lists and run statistics are stored for reproduction.

3) ADVERSARIAL VERIFICATION

This extends the source's stated denominator-51 check, but remains a finite calculation. Very large denominators necessitate integer arithmetic; no floating-point stopping criterion was used. Distinctness matters: $2/3$ cannot use $1/3$ twice under this convention, and instead follows denominators $3,5,9,45$. The parity lemma is valid even when distinctness forces a larger denominator; the bound $an-b<2a$ requires the extra condition stated above. Alternating parity by itself does not prohibit an infinite trajectory.

4) FINAL

UNRESOLVED. The finite range is verified with exact certificates and the numerator transition is explicit. No well-founded decreasing quantity proves universal termination, and no nonterminating admissible full-odd-set example is constructed.

5) SOURCES CHECKED

The complete supplied version, read 2026-09-23. Code and all computed trajectories: verification/batch_1_checks.py and verification/batch_1_checks.json. An official-page retrieval was unavailable; the algorithm convention is therefore specified rather than silently inferred.

6) COMPLETION ESTIMATE

Subjective progress toward termination for every admissible rational input. COMPLETION: 15%

Erdős Problem #282

1) FORMAL RESTATEMENT

Let $A\subseteq \mathbb{N}$ be infinite, and let $x\in(0,1)\cap\mathbb{Q}$. Consider the greedy procedure that repeatedly subtracts the largest unit fraction from the allowed set $\{1/n : n\in A\}$ that does not exceed the current remainder.

(Ambiguity and minimal correction.) As written in many informal descriptions, one chooses at each step the minimal $n\in A$ with $n\ge 1/x$ and replaces $x\leftarrow x-1/n$. For $A=\mathbb{N}$ this automatically yields distinct denominators (indeed a strictly increasing sequence), but for sparse $A$ one can obtain repeats. Since the goal is an Egyptian fraction (distinct denominators), the standard correction (used e.g. in the "odd greedy expansion" literature) is:

At step $j$, choose the least $n_j\in A\setminus\{n_1,\dots,n_{j-1}\}$ such that $\frac1{n_j}\le x_{j-1}$ (equivalently $n_j\ge 1/x_{j-1}$), and set $x_j=x_{j-1}-\frac1{n_j}$.

We call this the distinct-denominator greedy algorithm for $(x,A)$. It terminates if $x_t=0$ for some finite $t$, yielding \[ x=\sum_{j=1}^t \frac1{n_j},\qquad n_1<\cdots<n_t\in A. \]

Main question (Stein). With $A=2\mathbb{N}-1$ (the odd positive integers) and $x=a/b$ in lowest terms with $b$ odd: must the distinct-denominator greedy algorithm terminate?

Further questions included in the prompt.

1. Characterise pairs $(x,A)$ for which termination holds.
2. (Congruence classes) Fix $d\ge 1$ and $a\bmod d$. When $x=m/n$ admits a representation as a sum of distinct unit fractions with denominators $\equiv a\pmod d$ (Graham's condition), must the corresponding restricted greedy algorithm terminate?
3. (Squares) For $A=\{n^2:n\in\mathbb{N}\}$, Graham characterised exactly which $x$ admit a representation with distinct square denominators. Must the restricted greedy algorithm terminate for such $x$?

2) QUICK LITERATURE/CONTEXT CHECK

The problem for odd denominators is attributed to Stein and is widely stated as open (often called "Stein's conjecture" or the "odd greedy expansion problem"). It is known (Breusch--Stewart) that every rational with odd denominator admits some Egyptian fraction expansion with all denominators odd, but it is unknown whether the odd greedy choice always reaches such an expansion.

The problem page also records:

• Fibonacci $1202$ proved termination for $A=\mathbb{N}$ (the classical greedy/Sylvester algorithm).
• Graham gave a necessary-and-sufficient condition for existence of an expansion with denominators in a fixed residue class $\bmod d$.
• Graham also gave a necessary-and-sufficient condition for existence of an expansion with distinct square denominators, namely $x\in [0,\pi^2/6-1)\cup [1,\pi^2/6)$.

The question here is about termination of the greedy algorithm in these settings.

3) ATTACK PLAN

1. Invariant/obstruction search. Identify arithmetic invariants (e.g. parity, $p$-adic valuations, congruence constraints) that any finite $A$-Egyptian expansion forces on $x$. Use them to rule out termination for certain $(x,A)$ and to separate "existence of some expansion" from "greedy termination".
2. Termination proofs for subclasses. Prove termination for special families (e.g. $x=1/(2k+1)$, or bounded numerator, or specific congruence classes) by finding a monotone measure that decreases under the restricted greedy step.
3. Search for counterexamples (falsification). For the square-denominator and odd-denominator greedy variants, attempt to find a rational $x$ satisfying the known existence criteria but for which the greedy algorithm provably loops or generates an infinite series.
4. Understand known "long expansion" phenomena. For odd greedy expansions, huge denominators and long expansions occur (e.g. $3/179$). Try to extract a structural description of when the numerator sequence behaves regularly (consecutive integers), which may hint at non-termination mechanisms.

4) WORK

4.1. Classical case $A=\mathbb{N}$: termination proof (Fibonacci/Sylvester)

Let $x=a/b\in(0,1)$ in lowest terms. Set $n=\lceil b/a\rceil$ and define \[ x' = \frac{a}{b}-\frac1n = \frac{an-b}{bn}. \] Since $n-1< b/a\le n$, we have $a(n-1)<b\le an$, hence $0\le an-b < a$. If $an=b$ then $x'=0$ and we terminate. Otherwise, in lowest terms $x'=a'/b'$ has numerator $a'\le an-b < a$. Thus the numerator strictly decreases at each step, so termination occurs in at most $a$ steps.

4.2. A necessary obstruction for $A$ odd

4.3. Small computational sanity check for odd greedy termination

Implementing the distinct-denominator odd greedy algorithm (choose the least unused odd $n\ge 1/x$ each step), an exhaustive check over all reduced fractions $a/b\in(0,1)$ with odd $b\le 51$ found termination for every such fraction within at most $16$ steps. Some expansions have enormous final denominators even for modest $b$.

Warning: This is only evidence. There are known examples (e.g. $3/179$) where the odd greedy expansion has many terms and astronomically large denominators.

4.4. Congruence classes and squares

The prompt cites existence theorems (Graham) for Egyptian fraction representations with denominators restricted to a residue class $\bmod d$, and for representations with distinct square denominators. In both cases the open-ended question is: does the associated restricted greedy algorithm always terminate whenever a representation exists?

A basic necessary condition for greedy termination is of course existence of some expansion in the allowed denominator set; beyond that, there is no known general monotone quantity analogous to the numerator-decrease argument in §4.1.

5) VERIFICATION

• The proof in §4.1 is standard and fully explicit: the numerator decreases strictly.
• The parity obstruction in §4.2 is immediate from using an odd common denominator.
• The computational check in §4.3 was implemented with exact integer arithmetic and a "no-repeated-denominators" rule; it is exhaustive for odd denominators $\le 51$ but does not address larger denominators (where known blow-ups occur).

6) FINAL

UNRESOLVED.

1. Furthest point reached: proved basic necessary obstructions (even denominators impossible for odd $A$), recalled/verified classical termination for $A=\mathbb{N}$, and performed a complete finite check for all reduced $a/b$ with odd $b\le 51$ showing termination in these cases.
2. Key gap: no global invariant/monotone measure is found that forces termination (or yields a forced infinite trajectory) for $A=2\mathbb{N}-1$ with $b$ odd, nor for the congruence-class or square-denominator greedy variants.
3. Most promising next step: search for an explicit non-terminating example by exploiting "consecutive numerator" phenomena (as in long odd greedy expansions), or develop a Lyapunov-type function controlling the growth of denominators for restricted greedy steps.
4. Explicit missing lemma that would close it: either (a) a proof that every odd-denominator rational eventually reaches a unit fraction under the odd greedy update, or (b) an explicit $x$ with odd denominator for which the odd greedy remainder sequence never becomes $0$.

7) COMPLETION ESTIMATE

COMPLETION: 20%