Erdős problem #295 — wave 5r report

Access date: 2026-07-26 (UTC).

Claim labels used below:

• [a] elementary-rigorous: proved directly in this report.
• [b] rigorous-modulo-named-theorem: attributed to the named published

source.

• [c] plausible/structural-unverified: a heuristic or an incomplete

search, never used as a theorem.

• [d] computational-only: the stated finite result follows from the

complete exact computation and its reproducible checker.

0. Mandatory live-page gate

I fetched the rendered live page through the Bright Data browser path: Erdős Problems #295.

Live status: OPEN. The page says it was last edited 01 October 2025. It displayed 0 comments, 0 claimed proofs, “Interested in collaborating: None,” and “Currently working on this problem: None.” Therefore the mandatory skip condition did not trigger.

Here is the live statement verbatim (with the page's LaTeX preserved):

Let \(N\geq 1\) and let \(k(N)\) denote the smallest \(k\) such that there exist \(N\leq n_1<\cdots <n_k\) with \[ > 1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}. > \] Is it true that \[ > \lim_{N\to \infty} k(N)-(e-1)N=\infty? > \]

The only known result listed on the page is:

Erdős and Straus [ErSt71b] have proved the existence of some constant \(c>0\) such that \[ > -c < k(N)-(e-1)N \ll \frac{N}{\log N}. > \]

This quoted theorem is treated as [b], exactly as listed by the authoritative page.

1. Primary-source and current-literature check

The original 1980 source is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, scan. On printed page 35 it defines the same quantity (there called \(U_n\)), conjectures

and records

Its bibliography on printed page 113 identifies the source as P. Erdős and E. G. Straus, “Solution to Problem,” American Mathematical Monthly 78 (1971), 302–303. [b]

The journal record was independently resolved as problem E2232: JSTOR stable 2317539, DOI 10.2307/2317539. The live journal metadata gives H. D. Ruderman, P. Erdős, and E. Straus; volume 78, issue 3, March 1971, pages 302–303. The problem page's label [ErSt71b] and the monograph's local label [Er-Str (71) a] point to this same bibliographic item.

I searched exact strings including "k(N)-(e-1)N", variants with spaces, "E2232", the DOI, and combinations of “smallest number of terms,” lower denominator, and unit/Egyptian fractions. I also queried Crossref and OpenAlex by DOI. OpenAlex listed only two citing book chapters (1981 and 2004), not a later primary paper resolving or sharpening this particular limit. Searches did find nearby work on shortest expansions of a fixed rational and on bounding the largest denominator, but those are not the lower-cutoff function in this problem. Thus I found no later primary source that changes the live page's stated status. This is a scoped search miss, not a theorem that no such literature exists.

The related secondary entry OEIS A192881 currently tabulates through \(n=16\) the shortest expansion whose first denominator is exactly \(n\). That is not automatically identical to \(k(N)\), which permits its first denominator to be any integer at least \(N\). I use its \(n=16\) construction only as a source of a candidate identity; the checker below recomputes its sum from scratch and the lower-bound search directly uses the actual condition \(n_1\geq17\).

2. New concrete result

The verified output of this run is

The upper bound is an explicit elementary certificate [a]. The lower bound is a finite exhaustive exact-arithmetic result [d], with the completeness of the enumeration proved in Section 4 [a].

Equivalently, at this concrete point,

The decimal display is only for scale; it is not used in either proof.

3. Explicit 32-term construction

The following 32 distinct denominators are all at least 17:

Their reciprocal sum is exactly 1. [a]

A short way to see the construction is to begin with the independently checked 30-term identity

and use the exact four-for-two surgery

Removing \(16,40\) and inserting \(35,45,48,63\) gives the displayed 32-term set. The standalone checker sums both identities using fractions.Fraction; no floating-point arithmetic is involved.

4. Exhaustive lower bound \(k(17)\geq31\)

4.1 The analytic first cut

For any \(t\) distinct denominators

monotonicity of \(1/x\) gives

For \(t=28\), the right-hand side is exactly

Therefore no expansion with at most 28 terms exists. [a]

4.2 Finite recursion with no denominator cutoff

It remains to exclude 29 and 30 terms. Suppose a search state has positive rational remainder \(R\), needs \(t\geq2\) more terms, and its next denominator \(d\) must be at least \(L\). If a completion exists, then

The left inequality is strict at \(1/R\), because at least one positive term must remain after \(1/d\). The right inequality follows from

Thus every branch has a finite, explicitly enumerated range. [a]

After choosing \(d\), a branch is impossible whenever

because the left side is the largest possible sum from \(t-1\) distinct denominators greater than \(d\). [a]

For the last two terms write \(R=a/b\) in lowest terms. Every possible first denominator \(x\) lies in the finite interval from (1), and the second is forced:

The code checks exactly whether this is an integer with \(y>x\). Notice that \(y\) itself is not capped: it may be arbitrarily large if the exact arithmetic forces it. Hence this is not a bounded-denominator search. Together, (1), (2), and the forced last denominator prove that the recursion enumerates every possible expansion of the requested length. [a]

The completed run gave:

All remainders, harmonic maxima, divisibility tests, and final sums are exact integers/rationals. On this VM the two searches took about 0.02 s and 11.44 s respectively. Therefore 29 and 30 terms are impossible [d]. Combined with the 28-term inequality, \(k(17)\geq31\).

5. Independent checker

The standalone file is runs/erdos295_wave5r_verify.py. It uses only the Python standard library. Run it from the repository root:

python runs/erdos295_wave5r_verify.py

Its observed output was:

construction_length=32
construction_sum=1
maximal_28_term_sum=9344202253751673739/9419588158802421600
k=29: found=False; recursive_states=1667; two_term_states=910; two_term_candidates=3843; seconds=0.021
k=30: found=False; recursive_states=1461942; two_term_states=1119929; two_term_candidates=9197969; seconds=11.440
VERIFIED: 31 <= k(17) <= 32

Complete checker source:

#!/usr/bin/env python3
from fractions import Fraction
from functools import lru_cache

BASE_16 = (
    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
    32, 33, 34, 36, 38, 39, 40, 42, 43, 44, 50, 52, 54,
    1_735_650, 68_479_214_496,
)
CONSTRUCTION_17 = (
    17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
    32, 33, 34, 35, 36, 38, 39, 42, 43, 44, 45, 48, 50, 52,
    54, 63, 1_735_650, 68_479_214_496,
)

def reciprocal_sum(ds):
    return sum((Fraction(1, d) for d in ds), start=Fraction(0))

@lru_cache(maxsize=None)
def maximum_tail(lower, terms):
    return sum(
        (Fraction(1, lower + i) for i in range(terms)),
        start=Fraction(0),
    )

def search_for_expansion(minimum, terms):
    count = {"states": 0, "two_states": 0, "two_candidates": 0}

    def finish_with_two(remainder, lower):
        count["two_states"] += 1
        a, b = remainder.numerator, remainder.denominator
        first_x = max(lower, b // a + 1)
        last_x = (2 * b) // a
        for x in range(first_x, last_x + 1):
            count["two_candidates"] += 1
            num, den = a * x - b, b * x
            if den % num == 0 and den // num > x:
                return True
        return False

    def visit(remainder, lower, left):
        count["states"] += 1
        if maximum_tail(lower, left) < remainder:
            return False
        if left == 1:
            return remainder.numerator == 1 and remainder.denominator >= lower
        if left == 2:
            return finish_with_two(remainder, lower)
        first_d = max(
            lower,
            (1 / remainder).numerator // (1 / remainder).denominator + 1,
        )
        last_d = (left / remainder).numerator // (left / remainder).denominator
        for d in range(first_d, last_d + 1):
            new_remainder = remainder - Fraction(1, d)
            if maximum_tail(d + 1, left - 1) < new_remainder:
                continue
            if visit(new_remainder, d + 1, left - 1):
                return True
        return False

    return visit(Fraction(1), minimum, terms), count

assert reciprocal_sum(BASE_16) == 1
assert (
    Fraction(1, 16) + Fraction(1, 40)
    == Fraction(1, 35) + Fraction(1, 45)
       + Fraction(1, 48) + Fraction(1, 63)
    == Fraction(7, 80)
)
assert len(CONSTRUCTION_17) == 32
assert CONSTRUCTION_17 == tuple(sorted(set(CONSTRUCTION_17)))
assert min(CONSTRUCTION_17) == 17
assert reciprocal_sum(CONSTRUCTION_17) == 1
assert maximum_tail(17, 28) < 1
for k in (29, 30):
    found, counts = search_for_expansion(17, k)
    assert not found, (k, counts)
print("VERIFIED: 31 <= k(17) <= 32")

The standalone file contains the same algorithm with fuller comments, timings, and printed counters.

6. What remains and why this does not settle the limit

The harmonic maximum alone has threshold

as follows already from integral bounds for \(\sum_{n=N}^{N+t-1}1/n\). It therefore cannot make the excess tend to infinity; a uniform proof needs an arithmetic obstruction that forces an unbounded number of additional terms beyond the harmonic threshold. [a]

A basic such obstruction is that, in an exact identity summing to 1, for every prime \(p\mid L\), the largest value of \(v_p(n_i)\) must occur at least twice, where \(L=\operatorname{lcm}(n_1,\ldots,n_k)\). Indeed, multiply the identity by \(L\). If exactly one denominator has the largest \(p\)-adic valuation, exactly one summand \(L/n_i\) is nonzero modulo \(p\), whereas \(L\) is zero modulo \(p\), a contradiction. [a] The difficulty is converting these overlapping prime-by-prime requirements into a deficit that grows uniformly with \(N\); one added denominator can satisfy several requirements at once. That is the precise missing structural lemma.

Even the finite value \(k(17)\) is left with one bit unresolved: does a 31-term expansion exist? An exploratory run of the same exact recursion visited 5,000,000 states and tested 402,588,996 terminal \(x\)-values in 154.25 s without finding one, but it did not exhaust the tree and proves nothing about 31 terms [c]. At the observed mix, each further \(10^8\) recursion states would cost roughly 0.86 single-core hours; the total remaining frontier was not pre-counted, so assigning a total core-hour estimate would be speculation. A divisor-based solver for the last two terms or a stronger modular pruning lemma is the concrete next step. None of this finite work supplies the uniformity in \(N\) required by the live question.

PARTIAL: exact computation and an explicit certificate prove 31 <= k(17) <= 32, but the uniform Erdős limit and the 31-versus-32 case remain open.