Longest shortest Egyptian-fraction expansion: estimate N(b), is N(b) ≪ log log b? (Erdős #304)
Statement
For integers $1\le a<b$, let $N(a,b)$ denote the least $k$ for which there exist integers $1<n_1<\cdots<n_k$ with $$\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k},$$ i.e. the shortest length of an expansion of $a/b$ into distinct unit fractions. Put $N(b)=\max_{1\le a<b}N(a,b)$. Estimate $N(b)$; in particular, is it true that $N(b)\ll\log\log b$?
Acceptance. FULLY RESOLVES: a complete proof determining the order of $N(b)$ — in particular settling whether $N(b)\ll\log\log b$ (matching the lower bound) — machine-checkable (Lean, extending the existing formalisation) preferred, else a full written proof. ADVANCES (each independently checkable): (a) improve the upper bound strictly below Vose's $N(b)\ll\sqrt{\log b}$ with proof; (b) improve the lower bound strictly above $N(b)\gg\log\log b$ by exhibiting an explicit family of $b$ (with witnessing $a$) forcing longer shortest expansions, each accompanied by a certified shortest-length computation; (c) extend the tabulated exact values of $N(b)$ (and the associated OEIS sequences) to a new record $b$ with the search program and a proof of minimality for each reported expansion. Deliver the proof, or the construction + certified lengths, or the search code + tabulated maxima.
Background
Posed by Erdős and Graham [ErGr80, p.37]; listed as open on erdosproblems.com/304 (fetched 2026-07-21, status 'open'). Erdős [Er50c] proved $\log\log b\ll N(b)\ll\frac{\log b}{\log\log b}$. Vose [Vo85] sharpened the upper bound to $N(b)\ll\sqrt{\log b}$; the lower bound $N(b)\gg\log\log b$ still stands, and the conjecture is that this lower bound is the truth. On average the length is small: $\frac{1}{b}\sum_{1\le a<b}N(a,b)\gg\log\log b$. The problem is related to #18 (erdosproblems.com/18) and has a close connection — particularly through $N(b-1,b)$ — to #293 (erdosproblems.com/293), elucidated by van Doorn and Tang [vDTa25b] (2025). It has been formalised in Lean as part of the Google DeepMind Formal Conjectures project. OEIS A097847 and A097849 record related expansion-length data. Attacker's tool: certified computation of shortest distinct-unit-fraction expansions for all $a<b$ up to a large $b$ (dynamic programming / branch-and-bound over admissible denominators), extending the tabulated maxima and empirically probing the growth of $N(b)$, alongside analytic sharpening of Vose's $\sqrt{\log b}$ bound; the existing Lean formalisation supports a machine-checked resolution.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #304 (T. F. Bloom) | website |
| REF-02 | OEIS A097847 — Egyptian-fraction expansion data related to #304 | website |
| REF-03 | OEIS A097849 — Egyptian-fraction expansion data related to #304 | website |
| REF-04 | Lean formalisation of Erdős #304 (DeepMind Formal Conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.