#282: what the odd greedy algorithm does after the factorial runs out — K. S. Brown's 3/(500!−1) has exactly 501 terms, every 3/(N!−1) and 3/(2·N!−1) with N ≤ 3000 (and at N = 5,000 and 10,000) terminates within N + 60 terms, and every reduced a/b with odd b < 10,000 terminates, in at most 32; plus six OEIS entries whose data is rotated
The problem (erdosproblems.com/282; Erdős–Graham 1980, p. 30; the problem page credits the odd case to Stein). Take a fraction x = a/b in (0, 1) with b odd. Subtract the largest unit fraction 1/n with n odd and not used before, and repeat with what is left. Does this always stop? A finite sum of distinct odd unit fractions always exists (Breusch and Stewart, 1954); the question is whether the greedy choice finds one. On the problem's thread (7 July 2026) Thomas Bloom wrote that, although the 1980 book does not make it clear, he assumes the obvious rule is intended: at each stage take the largest such unit fraction not used so far.
What was known. The denominators roughly square at every step, so the expansions are enormous even when they are short. Stan Wagon noticed that 3/179 needs 19 terms, the last about 1.4·10439,491, and that the numerators of the remainders climb 3, 4, 5, …, 17 before falling to 2, 3, 4, 1. K. S. Brown explained the climb: while the remainder is n/(2m−1) with n dividing m, the next remainder is (n+1)/(2m′−1) with m′ = (m/n)(2m+n−1). He pointed out that the numerator sequence can still be computed, with modular arithmetic, when the denominators run to billions of digits, and he pointed Wagon to 5/5809, which a search for long expansions by David Bailey also turned up: 27 terms, numerators 5, 6, …, 30, 1. David Broadhurst added longer ones in 1999 (OEIS A031285: 5/1444613, 37 terms, the last with 384,122,451,172 digits). Brown observed that 3/(N!−1) climbs 3, 4, …, N, so expansions can be as long as you like. Jukka Pihko (Fibonacci Quarterly 39 (2001) and 48 (2010)) proved that the numerators alternate in parity, so a terminating expansion has length ≡ a (mod 2), counting the final unit fraction (the argument is the same under the not-used-before rule); that the fractions a/(2k+1) with k = −1 + t·a(a+1)···(a+n) climb at least to a+n (Theorem 2.3); and that 2/(2(p−1)!−1) has numerators exactly 2, 3, …, p−1, 1 for every odd prime p (Theorem 3.5; his algorithm allows a repeated denominator, and under #282's rule the same holds for every p ≥ 5). Bailey's search was exhaustive, in Brown's words, but its range is not recorded. The largest stated range we found is our own July report: every reduced a/b with odd b ≤ 999 terminates, in at most 27 terms.
Labels used below: (d) established by computation, reproducible from our bundle; (c) heuristic, not proved.
Brown's question. On his MathPages note Brown wrote: "It's interesting to consider the odd greedy expansion of a fraction such as 3/(500! - 1). We know this will contain at least 500 terms …, and the numerators of the remainders will be 4,5,6,...,500, but what will happen then?" And: "The interesting question is whether there might be some 'break-even point', so that a fraction like 3/(500!-1) might have enough initial divisibility to boost it into a sequence where, at least probabilistically, we would expect it to be able to continue generating the factors it needs indefinitely." A climb that never stopped would be a fraction whose odd greedy expansion never ends: a "no" to #282. We found no computation of what actually happens.
Ours: what happens (d).
- 3/(500!−1) has exactly 501 terms. Its numerators are 3, 4, …, 501, then 2, 1. The climb stops at 502 = 2·251. At numerator 501 the denominator is divisible by 251, so the next remainder, 502/(…), reduces by 251 to 2/(…). For that to happen, 500! must hold the prime 251 only once. Once its single copy has been spent at numerator 251, the denominator's residue mod 251 is free to move, and for this fraction it falls into the absorbing class 0 at numerator 378 (see below) and stays there. The climb never reaches 503, the first prime past 500. Holding 251 once is necessary, not sufficient: 3/(2·500!−1) also holds 251 once, its residue never reaches 0, and its climb passes 502.
- 3/(2·500!−1) (Brown's "m = 500!", the t = 2 case of Pihko's family) has 519 terms. The climb reaches 520, the prime 521 then divides the denominator, the next remainder is a unit fraction, and the expansion ends.
- For every N from 3 to 3000, both 3/(N!−1) and 3/(2·N!−1) terminate. The climb outruns N by at most 56 numerators (at N = 2,146, for 3/(N!−1)), on average by 5.87 and 7.31 for N ≥ 100. After the climb stops, at most 22 more numerators follow before the expansion ends, and every length is odd, as Pihko's parity theorem requires.
- 3/(5000!−1): 5,001 terms; the climb reaches 5,002, then 1.
- 3/(2·5000!−1): 5,001 terms; the climb reaches 5,002, then 1.
- 3/(10000!−1): 10,005 terms; the climb reaches 10,005, then 2, 1.
- 3/(2·10000!−1): 10,005 terms; the climb reaches 10,005, then 2, 1.
- 3/(20000!−1): 20,025 terms; the climb reaches 20,018, then 14755, 12058, 6695, 4714, 6445, 10666, 409, 196, 1 (certified; not in the table).
- 3/(2·20000!−1): 20,013 terms; the climb reaches 20,013, then 2, 1 (certified; not in the table).
| fraction | terms | climb reaches | how the climb stops | numerators after |
|---|---|---|---|---|
| 3/(10!−1) | 9 | 10 | 11 divides the denominator; the expansion ends | 1 |
| 3/(2·10!−1) | 13 | 13 | breaks at 13 (13 does not divide m) | 4, 1 |
| 3/(20!−1) | 21 | 21 | numerator 22 is cut by 11 to 2 | 2, 1 |
| 3/(2·20!−1) | 21 | 22 | 23 divides the denominator; the expansion ends | 1 |
| 3/(50!−1) | 59 | 60 | 61 divides the denominator; the expansion ends | 1 |
| 3/(2·50!−1) | 61 | 59 | breaks at 59 (59 does not divide m) | 74, 5, 4, 1 |
| 3/(100!−1) | 99 | 100 | 101 divides the denominator; the expansion ends | 1 |
| 3/(2·100!−1) | 109 | 107 | breaks at 107 (107 does not divide m) | 100, 157, 4, 1 |
| 3/(200!−1) | 205 | 201 | numerator 202 is cut by 101 to 2 | 2, 3, 4, 5, 2, 1 |
| 3/(2·200!−1) | 213 | 206 | breaks at 206 (206 does not divide m) | 359, 298, 253, 2, 3, 4, 5, 2, 1 |
| 3/(500!−1) | 501 | 501 | numerator 502 is cut by 251 to 2 | 2, 1 |
| 3/(2·500!−1) | 519 | 520 | 521 divides the denominator; the expansion ends | 1 |
| 3/(1000!−1) | 1,011 | 1,012 | 1,013 divides the denominator; the expansion ends | 1 |
| 3/(2·1000!−1) | 1,005 | 1,005 | numerator 1,006 is cut by 503 to 2 | 2, 1 |
| 3/(2000!−1) | 2,009 | 2,010 | 2,011 divides the denominator; the expansion ends | 1 |
| 3/(2·2000!−1) | 2,001 | 2,002 | 2,003 divides the denominator; the expansion ends | 1 |
| 3/(3000!−1) | 2,999 | 3,000 | 3,001 divides the denominator; the expansion ends | 1 |
| 3/(2·3000!−1) | 3,009 | 3,010 | 3,011 divides the denominator; the expansion ends | 1 |
| 3/(5000!−1) | 5,001 | 5,002 | 5,003 divides the denominator; the expansion ends | 1 |
| 3/(2·5000!−1) | 5,001 | 5,002 | 5,003 divides the denominator; the expansion ends | 1 |
| 3/(10000!−1) | 10,005 | 10,005 | numerator 10,006 is cut by 5,003 to 2 | 2, 1 |
| 3/(2·10000!−1) | 10,005 | 10,005 | numerator 10,006 is cut by 5,003 to 2 | 2, 1 |
Why the climbs end where they do (credited lens, not new). Write the denominator as z = 2m−1. One step of the climb sends z to z(z+n+1)/n. Fix a prime p. Whenever the numerator n is not a multiple of p, z mod p follows the same map mod p, and that map has two fixed points:
- z ≡ −1, that is, p divides m: p is no obstacle to the climb, which can still stop for some other reason (Brown's "covered"; his MathPages note kmath454 has the equivalent condition d ≡ ±1).
- z ≡ 0: p divides the denominator, and stays a divisor while the climb lasts. If the climb survives (other primes can still stop it) to numerator p−1, the next remainder is p/z′ with p dividing z′, a unit fraction, and the expansion ends with the following term. At a later multiple kp the same divisibility instead cuts the numerator kp down to k, as at 502 = 2·251. This invariant is the engine of Pihko's proof of his Theorem 3.5.
The map is two-to-one, so the residues collapse quickly. For p = 1009, the 1,009 possible residues at numerator 3 have reached just three states by numerator p: 670 covered, 257 fatal, 82 neither. For p = 2003, every residue is absorbed (596 covered, 1,407 fatal). The sweep shows how often each outcome happens: of the 5,802 climbs with 100 ≤ N ≤ 3000 (both families, classified from the certifier's own recomputed steps), 2,930 end the whole expansion: the number after the climb's last numerator R is a prime that divides the denominator (the fatal residue; it is never a composite). In 1,501, R divides m, but the next numerator R+1 shares a prime factor with the denominator and is cut down by it (like 502 → 2; always by a single prime). The other 1,371 break because R does not divide m (806 of them at a prime R). The number where the climb fails is the first prime past N in 2,541 cases, comes before it in 1,345 and lies past it in 1,916. The same computation, run Brown's way (does p divide m when the numerator reaches p, starting from every residue), reproduces his table of "favorable" residues exactly in 41 of its 44 rows, every prime from 13 to 199. In the rows for p = 5, 7 and 11 it differs only in the columns for starting numerator p−2 and p−1, where his counts are lower by 1 or 2. At p−1 he has 0, though the residue m ≡ 0 is always favorable. His count for 50! (6 of the 10 primes between 50 and 100) comes out only when the starting fraction is 3/(N!−1), that is m = N!/2; with the m = N! he states we get 4. His count for 100! (10) comes out either way, though there are 21 primes between 100 and 200, not 20. For 500! we get 36 of the 73 primes between 500 and 1000 either way, where he wrote "32 of the 64".
Is there a break-even point? (c), heuristic. Past N, every prime the climb meets, and every multiple of a prime whose copies in N! are spent, is a test the climb passes only if its own multipliers 2m+n−1 happened to supply the factor. The collapse above makes each test a toss with odds that vary from prime to prime: for the five primes we tabulated (101, 103, 503, 1009 and 2003), the covered share runs from 18% (p = 101) to 66% (p = 1009). Nothing visible makes them improve as N grows. So the chance of passing many tests in a row should fall off fast. The overshoot tends to grow with N, slowly and not steadily. Its mean over 500-wide bands of N runs 5.3, 5.8, 6.8, 7.1, 7.4 and then 6.7 for 2500 ≤ N ≤ 3000, and its overall maximum is 56, at N = 2,146. Nothing in the data points toward a break-even, but this is evidence, not proof. Proving that every 3/(N!−1) terminates would already be a theorem about an infinite family of very long expansions, and we do not have it.
Ours: the finite frontier, ten times further (d). Every reduced fraction a/b in (0, 1) with odd b < 10,000 terminates under the odd greedy algorithm, not-used-before rule included. That is 20,263,332 fractions (Σφ(b) over odd b, checked). The longest need 32 terms, and there are exactly four: 2086/2381, 7734/7829, 7990/8111 and 8328/8581. All four are large fractions where the not-used-before rule shapes the first steps. Along the way the numerators of three of them reach about 1.1–1.2·107; those of 2086/2381 peak at 115,811. Restricted to x < 1/3, where the not-used-before rule never binds and the classical examples live, there are 6,754,437 fractions. The unique longest is 373/6893, with 29 terms, and three need 28: 162/5809, 580/6563 and 1668/8069. Bailey and Brown's 5/5809 is one of four 27-term fractions in range. Our July report's bound was b ≤ 999 (27 terms, at 881/937). The largest independent range we found is all b ≤ 199 (an unreviewed GitHub repository).
An aside: six OEIS entries have their data rotated. OEIS A030541–A030546 (David Broadhurst, 1999) each list the remainder numerators of one fraction. In every one of the six, the data is the exact sequence of the fraction named in the previous entry, wrapping around: A030541, named 2/588391, lists 5, 6, …, 30, 1, which is 5/5809's sequence. A030546, named 5/5809, lists 6/104651's. Broadhurst's A031285 (5/1444613) is correct. Both of our engines agree on all seven sequences.
What this does not do. It proves nothing about termination in general, or for any infinite family. Its numbers are finite. It does not touch the general question of which pairs (x, A) terminate, or the squares variant, where Erdős and Graham suspected the greedy algorithm fails to terminate, perhaps almost always. The problem stays open.
How it was checked. Three engines, written separately. og.c (C with GMP) follows the numerators by recomputing the exact starting denominator modulo whatever each step needs, and asserts every division. It runs in two modes: one replays from the start at every step; the other carries a predicted modulus forward and replays only when a prediction fails. check_fixedmod.py (Python with gmpy2) uses one fixed modulus and no replay, and stops rather than guesses if a numerator outgrows it. certify.py recomputes every step of a claimed trajectory from the starting fraction and uses the claim only to size its modulus. Plain exact arithmetic with the real denominators covers N ≤ 19. The certifier independently re-derives all of the 5,996 sweep rows, and the rows for N = 5,000 and 10,000, step by step; the endings counted above come from its own recomputed steps, not from og. The engines agree as follows. The two og modes give identical full numerator sequences for every N ≤ 400 in both families, and identical rows near N = 2000. The fixed-modulus engine matches og in full at N = 500 and 1000. Exact arithmetic matches every length for N ≤ 19. og reproduces our July exact checker's length histogram for b ≤ 999 to the last count. The four 32-term records, the 29-term 373/6893, July's 27-term 881/937 and 3,000 random fractions with b < 104 are all certified. Every single-position corruption of five claims (109 in all) is rejected. An earlier version of the certifier skipped the not-used-before prefix and accepted one corruption, which that same control caught; it was fixed. Literature controls, all reproduced exactly: Wikipedia's 4/23, Wagon's 3/179, Brown's 5/139 and 5/5809, Broadhurst's A031285 and his six A03054x sequences (under rotated names), Pihko's Table 4 (3/(24t−1), t ≤ 10) and his Theorem 3.5 for every odd prime 5 ≤ p < 400. Mutations: flipping the parity rule changes the histogram, and setting every gcd to 1 trips the coprimality assertion on the first fraction. A hostile referee seat (Opus, with tools) built two engines of its own: a per-prime residue engine, and a fully exact one that keeps the real set of used denominators. It confirmed the hand-off, the modular bookkeeping and every length it re-ran (N = 30 to 1777 and both N = 5,000 rows; its exact engine matches og on all 32,364 fractions with b < 400). It also checked the two fixed points on 1.6 million steps of the map. It found two problems. og's printed sequence left out the prefix numerators; lengths were unaffected, it is fixed, and re-running 996 sweep rows changed one, N = 3. And our first explanation of 502 gave a necessary condition as the cause. The mechanism above is the referee's finding, and our own residue tracker reproduces it. A literature seat found Pihko's two papers, which moved parity alternation and the fixed points from "ours" to "credited". An independent unreviewed check of all b ≤ 199 (8,150 fractions, at most 21 terms, at 191/197) agrees with og. A blind read of the draft found sixteen further problems, all fixed before publication (the full list is in the bundle). Among them: our first count of how climbs end put every break at the number after the climb, and so misplaced about 1,400 of them; it is now taken from the certifier. A check that "every composite stop needs a prime N! lacks" was vacuous, since every number past N has one, and it is gone. A sentence wrongly had Thomas Bloom vouching for the 1980 book. Brown's 50! count matches only with m = N!/2. The heuristic said the odds do not change with N, which the data does not support. A second blind read of the revised page corrected six more statements. run_controls.sh re-runs every control (output in controls.txt); certify_sweep.py with gen_stats2.py re-runs the certifier over the sweep. Files: our bundle.