Erdős Problem #304

Problem #304

1) ROUND-2 OBJECTIVE

Path C (obstruction/correction). Round 1 did not produce a rigorous theorem beyond the classical literature bounds. The most promising round-2 target is therefore a sharp subproblem. I will do two things:

1. prove a complete theorem for the prime-denominator boundary case $(p-1)/p$, namely that no three-term Egyptian decomposition exists for any prime $p\ge 11$;
2. prove that a natural reduction suggested by the Round 1 data --- namely "the worst case should always be $(b-1)/b$" --- is already false at $b=79$.

2) Round-1 FOUNDATION USED

I use the following Round 1 material.

1. Every rational $0<a/b<1$ has some Egyptian-fraction decomposition with distinct denominators.
2. The exact-search framework from Round 1 computes $N(a,b)$ by iterative deepening with safe pruning.
3. Round 1 already established the exact value $N(79)=6$ with witness $a=77$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is the exact two-term criterion \[ \frac{u}{v}=\frac1x+\frac1y \quad\Longleftrightarrow\quad (ux-v)(uy-v)=v^2 \] for $(u,v)=1$. Applied to the remainder after peeling off $1/2$, this turns the "three terms?" question for $(p-1)/p$ into a finite divisor congruence problem over divisors of $4p^2$.

4) ATTACK PLAN (ROUND-2)

The precise gap after Round 1 was the lack of a rigorous lower bound even for special infinite families of denominators. To close that gap I will:

1. prove the two-term criterion carefully;
2. show that any hypothetical three-term decomposition of $(p-1)/p$ with $p\ge 11$ must start with $1/2$;
3. reduce the remainder to the two-term criterion and rule it out by congruence;
4. then use the exact-search machinery from Round 1 for one new check, namely $N(78,79)=5$, in order to disprove the tempting simplification "study only $(b-1)/b$".

5) WORK (ROUND-2)

Lemma (two-term criterion). Let $0<u<v$ with $(u,v)=1$. Then \[ \frac{u}{v}=\frac1x+\frac1y \] for some integers $1<x<y$ if and only if there exists a divisor $d\mid v^2$ such that \[ u\mid (v+d). \] In that case one may take \[ x=\frac{v+d}{u}, \qquad y=\frac{v+v^2/d}{u}. \]

Proof. Starting from \[ \frac{u}{v}=\frac1x+\frac1y, \] clear denominators to get \[ uxy=v(x+y). \] Rearranging gives \[ (ux-v)(uy-v)=v^2. \] So if a two-term decomposition exists, then $d:=ux-v$ is a divisor of $v^2$, and clearly $u\mid (v+d)$. Conversely, assume $d\mid v^2$ and $u\mid (v+d)$, and set $e:=v^2/d$. Because $(u,v)=1$ and $d\mid v^2$, we also have $(u,d)=1$. From $d\equiv -v\pmod u$ and $de=v^2$ it follows that \[ e\equiv v^2 d^{-1}\equiv -v\pmod u. \] Hence both $(v+d)/u$ and $(v+e)/u$ are integers, and substituting them into \[ (ux-v)(uy-v)=v^2 \] shows that they indeed give a two-term Egyptian decomposition. $\square$

Theorem. Let $p\ge 11$ be prime. Then $(p-1)/p$ has no three-term Egyptian-fraction decomposition. Equivalently, \[ N(p-1,p)\ge 4 \qquad (p\ge 11\text{ prime}). \] Therefore the only primes with $N(p-1,p)\le 3$ are \[ p=2,3,5,7. \]

Proof. Suppose for contradiction that \[ \frac{p-1}{p}=\frac1x+\frac1y+\frac1z \] with integers $1<x<y<z$. If $x\ge 3$, then \[ \frac1x+\frac1y+\frac1z\le \frac13+\frac14+\frac15=\frac{47}{60}, \] whereas for $p\ge 11$, \[ \frac{p-1}{p}\ge \frac{10}{11}>\frac{47}{60}. \] So necessarily $x=2$. Subtracting $1/2$ gives \[ \frac{p-2}{2p}=\frac1y+\frac1z. \] Now $p$ is odd, so \[ (p-2,2p)=1. \] Apply the lemma with \[ u=p-2, \qquad v=2p. \] Then there must exist a divisor $d\mid 4p^2$ such that \[ p-2\mid 2p+d. \] Every divisor of $4p^2$ is of the form $2^i p^j$ with $0\le i,j\le 2$. Modulo $p-2$ we have $p\equiv 2$, hence \[ d\equiv 2^{i+j}\pmod{p-2}. \] Therefore the divisibility condition implies \[ p-2\mid 4+2^{i+j}. \] But $i+j\in\{0,1,2,3,4\}$, so the right-hand side can only be one of \[ 5,\ 6,\ 8,\ 12,\ 20. \] Since $p\ge 11$ is odd prime, $p-2$ is an odd integer at least $9$, and no such integer divides any of $5,6,8,12,20$. Contradiction. Hence no three-term decomposition exists.

For the small prime exceptions we have explicit decompositions \[ \frac12=\frac12, \qquad \frac23=\frac12+\frac16, \] \[ \frac45=\frac12+\frac14+\frac1{20}, \qquad \frac67=\frac12+\frac13+\frac1{42}. \] Thus the only primes with $N(p-1,p)\le 3$ are $2,3,5,7$. $\square$

A concrete obstruction to the "just study $(b-1)/b$" strategy. Using the exact iterative-deepening search from Round 1, I checked that \[ N(78,79)=5, \] for example via \[ \frac{78}{79}=\frac12+\frac13+\frac17+\frac1{90}+\frac1{24885}, \] and the same exact search shows that no four-term decomposition exists. Round 1 already established \[ N(77,79)=6. \] Therefore, even at the same denominator $b=79$, the extremal numerator is not $a=b-1$. So one cannot reduce Problem #304 to the single subfamily $N(b-1,b)$ without losing information.

6) ADVERSARIAL VERIFICATION

1. Did the proof really force $x=2$? Yes. The bound $1/3+1/4+1/5=47/60$ is the maximum possible three-term sum with $x\ge 3$, and $(p-1)/p\ge 10/11$ for every prime $p\ge 11$.
2. Was the two-term criterion applied in reduced form? Yes. For odd prime $p$, $(p-2,2p)=1$, so the lemma applies exactly as stated.
3. Were all divisors of $4p^2$ considered? Yes. Every divisor is $2^i p^j$ with $0\le i,j\le 2$, so $i+j\in\{0,1,2,3,4\}$.
4. Could the computational side remark hide a gap? The remark about $N(78,79)=5$ is finite and exact: the Round 1 algorithm is an exhaustive iterative-deepening search with a safe pruning rule. It found the displayed five-term representation and found no four-term representation.
5. Does the theorem solve the original asymptotic problem? No. It solves only a prime-denominator boundary subproblem, but it is a genuine new theorem on an infinite family.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED). Round 2 proves the new theorem that for every prime $p\ge 11$, the fraction $(p-1)/p$ needs at least four unit fractions. Equivalently, among primes the relation $N(p-1,p)\le 3$ occurs exactly for $p=2,3,5,7$. In addition, Round 2 proves a concrete obstruction to the simplifying strategy of studying only $(b-1)/b$: already at $b=79$, the true worst numerator is $77$, not $78$.

8) COMPLETION ESTIMATE

COMPLETION: 27%

9) REFERENCES

• Round 1 output in this conversation (used as fixed foundation, including the exact value $N(79)=6$).
• T. F. Bloom, Erdős Problem #304.
• W. van Doorn and Q. Tang, The smallest denominator not contained in a unit fraction decomposition of $1$ with fixed length, arXiv:2512.22083.

Erdős Problem #304: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

Let $N(a,b)$ be the least number of distinct unit fractions with denominators greater than one representing $a/b$, and $N(b)=\max_{1\le a<b}N(a,b)$. Is $N(b)=O(\log\log b)$?

All supplied versions considered: 304.tex. The source proves a fixed lower bound for prime boundary fractions and asserts exact values at denominator 79. I repair its ordered two-term parametrization and independently verify those finite assertions; this does not address the asymptotic upper bound.

2) WORK

For reduced $u/v>0$, a representation $u/v=1/x+1/y$ with $2\le x<y$ corresponds exactly to divisors \[ d\mid v^2,\quad 0<d<v,\quad u\mid v+d,\quad x=(v+d)/u\ge2, \] with $y=(v+v^2/d)/u$. Indeed $(ux-v)(uy-v)=v^2$, and $x<y$ gives $d<v$. Conversely the congruence on $d$ implies that on $v^2/d$ because $(u,d)=1$, and $d<v$ gives strict ordering. The source omitted this ordering restriction in its displayed construction.

For a general search with residual fraction $r>0$ and $k>1$ remaining terms whose denominators begin at $s$, every first denominator satisfies \[ \max\{s,\lfloor1/r\rfloor+1\}\le x\le\lfloor k/r\rfloor. \] The lower inequality leaves a strictly positive residual; the upper follows from $r\le k/x$. Recursing with exact fractions and increasing denominators is therefore complete. For $k=1$, a representation exists precisely when $1/r$ is an integer at least $s$.

The saved implementation verifies $N(78,79)=5$ and $N(77,79)=6$, finding respectively \[ (2,3,7,90,24885),\qquad(2,3,8,62,4524,7386184) \] as denominator lists, and exhaustively rejecting all shorter lengths. Thus the largest numerator need not be hardest even at one fixed denominator. No claim that 77 maximizes over all numerators is needed for this counterexample to the boundary-only strategy.

3) ADVERSARIAL VERIFICATION

The search has a proved finite range at every node, uses exact rational residuals, and enforces distinct denominators. Fixed examples and fixed lower bounds do not establish a logarithmic-logarithmic upper bound for all $b$.

4) FINAL

UNRESOLVED. The required uniform short decompositions for arbitrary numerators and denominators remain missing. This attempt supplies a corrected finite decision procedure and independently checked local evidence only.

5) SOURCES CHECKED

Full 304.tex read; asymptotic target checked in formal-conjectures ErdosProblems/304.lean, 2026-09-23. Exact search executed with verification/batch_2_checks.py.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 8%

Problem #304

1) FORMAL RESTATEMENT

For integers $1\le a<b$, let $N(a,b)$ denote the least $k\in\mathbb{N}$ for which there exist integers \[ 1<n_1<n_2<\cdots<n_k \] with \[ \frac{a}{b} = \frac{1}{n_1}+\frac{1}{n_2}+\cdots+\frac{1}{n_k}. \] Define the extremal quantity \[ N(b):=\max_{1\le a<b} N(a,b). \] The problem asks for asymptotics of $N(b)$ as $b\to\infty$, and in particular whether \[ N(b) \ll \log\log b \] holds.

2) QUICK LITERATURE/CONTEXT CHECK

From the ErdosProblems #304 page and standard references (Erdős--Graham 1980; Vose 1985; surveys), the state recorded in the prompt is:

• Erdős proved a lower bound of order $\log\log b$ and an upper bound of order $\frac{\log b}{\log\log b}$ for $N(b)$, and moreover that the average of $N(a,b)$ over $a$ is $\ge c\log\log b$.
• Vose $1985$ improved the upper bound to $N(b)\ll \sqrt{\log b}$.
• A 2025 preprint of van Doorn--Tang (arXiv:2512.22083) discusses related extremal questions and notes connections back to #304.

I did not find a definitive resolution of the conjecture $N(b)\ll \log\log b$ in this quick check.

3) ATTACK PLAN

1. Existence baseline: recall/prove that every rational $a/b$ has some Egyptian-fraction decomposition with distinct increasing denominators.
2. Upper-bound route: attempt to build a decomposition algorithm with provably few terms (ideally $O(\log\log b)$).
3. Lower-bound route: search for explicit families of $b$ and $a$ that force many terms; understand how the squarefree kernel/prime factor structure constrains decompositions.
4. Computation for small $b$: compute $N(b)$ exactly for small $b$ using backtracking bounds, to get a sanity check on growth.

4) WORK

4.1. Every rational has an Egyptian-fraction decomposition (classical).

The greedy algorithm (Sylvester expansion) shows that every rational $0<a<b$ can be written as a finite sum of distinct unit fractions. Sketch: set $x_0=a/b$ and iteratively define \[ n_i := \left\lceil \frac{1}{x_{i-1}}\right\rceil,\qquad x_i := x_{i-1} - \frac{1}{n_i}. \] Then $x_i$ remains a nonnegative rational, the denominators $n_i$ are strictly increasing, and the numerator of $x_i$ (in lowest terms) strictly decreases whenever $x_i\ne 0$, so the process terminates. Thus $N(a,b)$ is always finite.

4.2. Exact computation for small $b$.

I implemented an iterative-deepening DFS for $N(a,b)$ using the standard pruning bound \[ \frac{a}{b}\le \frac{k}{n}\quad\Rightarrow\quad n\le \frac{k b}{a} \] for the next denominator $n$ when $k$ terms remain (a safe relaxation since $\frac1n+\cdots+\frac1{n+k-1}<k/n$). Using this, I computed $N(b)$ for $2\le b\le 50$. The maximum in this range is small (at most $6$). For example: Moreover, scanning $b\le 300$ found the largest value $N(b)=6$ at $b=79$ (with witness $a=77$). These small computations do not meaningfully distinguish between $\log\log b$, $\sqrt{\log b}$, etc., but they are consistent with very slow growth.

5) VERIFICATION

• The greedy-algorithm termination argument is standard: at each step $x_i=\frac{a_i}{b_i}$ with $0<a_i<b_i$ and choosing $n_i=\lceil b_i/a_i\rceil$ makes the new numerator $a_{i+1}=a_i n_i-b_i$ satisfy $0\le a_{i+1}<a_i$.
• The pruning inequality $n\le (k b)/a$ used in the brute-force search is valid because any $k$-term tail with denominators $\ge n$ sums to $<k/n$.
• The computed $N(b)$ values were cross-checked by rerunning with larger search caps; no instances up to $b=50$ required more than $6$ terms.

6) FINAL

UNRESOLVED.

1. Progress achieved. I restated the problem precisely, recalled a proof that $N(a,b)$ is always finite (greedy Egyptian fractions), and computed exact values of $N(b)$ for small $b$ (up to $50$, and tracking maxima up to $300$).
2. Where it got stuck. No new asymptotic upper/lower bound beyond the literature-recorded ones (Erdős; Vose) was proved here. In particular, I did not prove nor disprove $N(b)\ll \log\log b$.
3. What next steps would look like. On the upper-bound side, one would try to refine constructive algorithms (perhaps using carefully chosen "smooth" denominators) to push $\sqrt{\log b}$ down toward $\log\log b$. On the lower-bound side, one would seek explicit families of $b$ and $a$ whose decompositions force many distinct denominators, potentially via local obstructions modulo many primes.
4. Falsifiable conjecture. The conjecture suggested in the prompt and surveys is that $N(b)=O(\log\log b)$, and perhaps even $N(b)\asymp \log\log b$.

7) COMPLETION ESTIMATE

A resolution would require either a construction giving an $O(\log\log b)$-term decomposition for every $a/b$ (uniformly in $a$), or a counterexample family of $b$ for which some $a/b$ provably needs $\omega(\log\log b)$ terms. Either direction seems to demand ideas beyond current elementary decomposition algorithms.