#295: k(17) = 32, and now 33 ≤ k(18) ≤ 35 by exact exhaustion

The target (erdosproblems.com/295, OPEN). Let k(N) be the fewest distinct increasing denominators N≤n₁<⋯<n_k whose reciprocals sum to 1. Erdős asked whether

k(N)−(e−1)N → ∞.

We did not solve that asymptotic question.

Round 2 (11 August): the next cutoff is narrowed to three values. The new exact computational result is

33 ≤ k(18) ≤ 35.

The elementary part of the lower bound. Among any t distinct denominators at least 18, the largest reciprocal sum comes from the consecutive integers 18,…,17+t. For t=30 that sum is exactly

442017301628992345493 / 442720643463713815200 < 1.

Thus 30 or fewer terms are impossible. At 31 terms the harmonic maximum crosses 1, so the next two lengths require a genuine exhaustive search.

The exact exclusions at 31 and 32. The same finite recurrence proved below was implemented twice: once with GMP integers and rationals and a static threaded frontier, and once with Python arbitrary-size integers and fractions.Fraction using a different multiprocessing split and terminal implementation. Both completed with no expansion and exactly the same counters:

• 31 terms: 20,293 states, 13,139 two-term states, and 69,727 scanned first denominators;
• 32 terms: 14,678,224 states, 11,753,049 two-term states, and 114,603,091 scanned first denominators.

The terminal formula forces the last denominator algebraically and never caps it. Both engines were separately tested on a completion whose forced last denominator is 10¹⁰⁰. Every branch deletion is an exact rational comparison; floating point can only retain extra work. The optional factorization path was never reached in either proof run.

The 35-term upper certificate. Starting from the Round-1 identity, replace 1/17 by

1/31 + 1/40 + 1/640 + 1/337280 = 1/17.

This gives the following 35 strictly increasing denominators, all at least 18, whose reciprocals sum exactly to 1:

18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 44, 45, 48, 50, 52, 54, 63, 640, 337,280, 1,735,650, 68,479,214,496.

The replacement is itself an integer certificate: (10880+8432+527+1)/337280=19840/337280=1/17. Exact Fraction arithmetic checks the complete source identity, the surgery, strict ordering, and the new complete sum.

Audit posture. A hostile audit rebuilt and reproduced the whole package, reran the full 32-term search under AddressSanitizer and UndefinedBehaviorSanitizer, checked the threaded search under ThreadSanitizer, and reran the Fraction engine serially with multiprocessing removed. It found no load-bearing gap. The two engines share the same proved recurrence lineage, so their agreement is an arithmetic and implementation cross-check, not a second mathematical method. Accordingly, k(18)≥33 is labelled a rigorous computational result, not an elementary proof.

What remains at 18. We have not found a 33- or 34-term identity, nor excluded either length; k(18) could be 33, 34, or 35. None of these finite computations settles the original asymptotic question.

Round 1: the first missing finite value. We closed the first undecided finite value beyond the existing tables:

k(17)=32.

The upper certificate. The following 32 distinct denominators are increasing, begin at 17, and have reciprocal sum exactly 1:

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.

Their least common multiple is L=200,301,702,400,800, and direct integer addition gives ΣL/d=L. Thus k(17)≤32 with no numerical approximation.

Why the lower search is finite. At a state with positive reduced remainder R=a/b, t terms left, and next denominator at least D, every possible first denominator d lies in the exact interval

max(D,⌊b/a⌋+1) ≤ d ≤ ⌊tb/a⌋.

The left inequality leaves room for a positive tail; the right follows from R≤t/d. After choosing d, the largest possible sum of the remaining distinct fractions is 1/(d+1)+⋯+1/(d+t−1). If that is smaller than R−1/d, the branch is impossible. Moreover 1/d plus this maximal tail decreases strictly with d, so the first failure discards every later child. These are exact rational tests.

The unbounded final denominator is not truncated. For the last two terms, an ordered solution D≤x<y of a/b=1/x+1/y is equivalent to

(ax−b)(ay−b)=b².

Writing q=ax−b, the program either scans every admissible x or enumerates every divisor q of b² with q<b, q≡−b (mod a), and q≥aD−b. Then x=(b+q)/a and y=(b+b²/q)/a. This covers arbitrarily large y; there is no hidden denominator cap.

The exact exclusion. The 28 largest possible terms already sum to 9,344,202,253,751,673,739 / 9,419,588,158,802,421,600, which is below 1. The exhaustive runs then returned:

• 29 terms: 1,667 states, none;
• 30 terms: 1,461,942 states, none;
• 31 terms: 447,526,713 states, 382,969,084 two-term states, 5,721,929,705 direct-scan candidates, none.

Only two terminal ranges were wide enough for divisor enumeration. They used b=219,060,189,739,591,200 and b=9,419,588,158,802,421,600, both factoring completely over the displayed small primes in the verifier log. A separate standard-library Python meet-in-the-middle enumeration checked respectively 11,366,932 and 34,100,797 divisors below b in the required residue classes and found none.

Audit posture. We ran the 31-term computation three times across two C++ implementations and different thread counts; every state and candidate total agrees exactly. The newest implementation uses a fixed 18,727-task frontier with atomic exactly-once assignment. Floating point can only retain extra work: every actual branch deletion is confirmed by GMP exact arithmetic. An adversarial code review found no skipped branch, overflow on this instance, or race. The implementation is decorrelated, not an algorithmically independent method — its author had read the earlier depth-first searches — so the lower bound remains an exact computational result, not an elementary proof.

The OEIS connection. A192881 asks for the shortest expansion whose first term is exactly 1/n and currently ends at n=16. The lower search allows the first denominator to be any value at least 17, while our upper identity actually starts at 17. Therefore the same result also gives a(17)=32.

What remains. The original problem needs a uniform arithmetic obstruction forcing k(N)−(e−1)N to grow. Exact recursion scales exponentially and does not provide that. The persistent structural clue is p-adic: for every prime in the common denominator, the largest denominator valuation must occur at least twice. No known argument yet turns those overlapping prime-by-prime constraints into an unbounded global excess.