A reader, who shall remain anonymous, said: "I do not think the 3/179 problem is a very good Problem of the Week". Yet it has stimulated far more correspondence than any other problem this year!Theorem [Breusch and Stewart, 1950s]: Every m/n, where n is odd, is a sum of distinct odd unit fractions.
Famous unsolved problem (see [Guy, Unsolved Problems in Number Theory, Springer; or Klee & Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, MAA]: Does the odd greedy algorithm for getting a representation of m/n (n odd) as a sum of distinct odd unit fractions terminate always? ("Greedy" means: at each step chose the largest 1/m that will fit, with m odd and different from previous choices.)
My PoW was motivated by my discovery a year ago that 3/179 gives quite interesting results on the odd greedy algorithm! It yields 19 terms, beginning with:
63, 2731, 5963959, . . .The last term has almost 500,000 digits! More amazing, the numerators of the remainders (which decrease in the unrestricted greedy algorithm), are3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1Quite a pattern! What is going on?Now, some correspondents last year found better representations: Kevin Brown (Seattle) found: 63, 1611, 3759 and Milo Gardner (Sacramento) found: 63, 1253, 11277.
Several of you (Ron Hardin, AT&T Labs, Research; John Guilford, HP, Everett, Wash.; David Eppstein, UC Irvine Dept. of Information & Computer Science; Charles Rees, Univ. of New Orleans) found Brown's answer, so it might well be the case that Brown's solution is the simplest 3-term representation there is. [It is. See below.] There is no 2-term rep'n (exercise).
Some of you might be interested in the question of what algorithms the Egyptians used when computing Egyptian fractions. Many of them are immortalized on the Rhind papyrus, and Milo Gardner has made an extensive investigation. Contact him for details at gardnerm@ecs.csus.edu.
Eppstein also found that 3/179 =
1/171 + 1/209 + 1/285 + 1/895 + 1/1611 + 1/1969 + 1/2685which might be the smallest max-denominator. [It is.]Eppstein's home page has misc. Egyptian fraction stuff (http://www.ics.uci.edu/~eppstein/numth/egypt/) and his article in Mathematica in Education and Research [vol 4, no. 2, 1995, pp 5-15] discusses Mathematica implementations of a variety of algorithms. I guess I should throw my own code down. It implements the odd greedy method, together with an option for seeing the numerators of the remainders, which might, if a proof is ever found, play a role in the proof that this halts. The code is from a revision of my book Mathematica in Action (Springer).
------------------------------------------------------------ Mathematica Code for odd greedy algorithm. Note the options, which are useful in large computations. ------------------------------------------------------------ OddGreedyEF::pastmx = "The maximum size of a term has been exceeded, so the result is only partial."; OddGreedyEF::usage = "OddGreedyEF[q] returns the representation of the rational q as an Egyptian fraction using odd denominators. The input must have an odd denominator."; MaxTerm::usage = "MaxTerm is an option to OddGreedyEF that stops the computation when the terms get beyond the setting. Remember to use, for example, 10.^10000, not 10^10000."; PrintPartialResults::usage = "PrintPartial results is an option to OddGreedyEF that causes the terms, and perhaps the remainder-numerators to be shown as the computation proceeds."; ShowNumerators::usage = "ShowNumerators is an option to OddGreedyEF that causes the output to include the numerators of the remainders."; Options[OddGreedyEF] = {ShowNumerators -> False, PrintPartialResults -> False, MaxTerm -> Infinity}; OddGreedyEF[0, oldMax_, opts___] := {{}, {}} OddGreedyEF[q_, oldMax_Integer:1, opts___Rule] := Module[ {m = Max[oldMax + 2, Ceiling[1/q]]}, {numQ, prQ, mx} = {ShowNumerators, PrintPartialResults, MaxTerm} /. {opts} /. Options[OddGreedyEF]; If[oldMax == 1, nums = {}]; If[!numQ && oldMax == 1, First, Identity][ {Prepend[If[EvenQ[m], m++]; If[numQ, AppendTo[nums, Numerator[q]]]; If[prQ, Print[{N[m], Numerator[q]}]]; If[m > mx, Message[OddGreedyEF::pastmx]; { }, First[OddGreedyEF[q - 1/m, m, opts]]], m], nums}]] /; OddQ[Denominator[q]]Now, Neil Sloane and Ron Hardin (AT&T) conjecture that every 3/b (b not divisible by 3) has a 3-term representation as a sum of distinct odd unit fractions. This is clearly true in the unrestricted case (greedy algorithm, numerators of remainders decrease!). Their conjecture nicely complements famous conjectures in this area:
Richard Guy (Calgary) observes: 3/(6n+1) = 1/(2n+1) + 1/(2n+1)(4n+1) + 1/(4n+1)(6n+1), and some others along these lines.
- 4/n has a 3-term representation. (Erdos and Straus)
- 5/n has a 3-term represntation (Sierpinski)
David Bailey (NASA Ames), using customized high-precision arithmetic on an SGI work station and aware of my desire to "stump" the odd greedy algorithm, found the following monster: 3/2879. The odd greedy rep'n has 21 terms; the last term has 3,018,195 digits; and the sequence of numerators of the remainders is
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 1I believe with this computation David gets the record for the largest Egyptian fraction computation ever done. I think my 3/179 was a record when I did it last year. Nice!
Eppstein then found: 1/963 + 1/308053 + 1/2772477 and 1/1615 + 1/5355 + 1/14395 + 1/20153 + 1/25911 + 1/43185 + 1/48943 + 1/54701 + 1/60459 for this example, the latter being the unique example with min-max-denominator.
It would be nice to have some heuristics to predict where the bad examples for the odd greedy algorithm are. In particular, I would like one that stumps David Bailey's software in the sense that he will be unable to tell whether the algorithm halts.
Late News: Boy, #847 generated a lot of correspondence! David Bailey reports that 5/5809 stumps his program, which is limited to about 15,000,000,000-digit precision. He gets:
1/163 + 1/1125979 + [21 terms omitted] + 1/s + ...where the integer s is approximately 6.875 x 1012565952. So here we have an example of a conceptually very simple algorithm, and a specific input, and we have no idea, and may never have any idea, whether the algorithm halts. This is very nice indeed.Of course, I have no doubt that nice rep'ns exist. The issue is that odd greedy is very mysterious.
The remainder-numerators for 5/5809 look like: 5, 6, 7, 8,.... 20, 21, which is as far as I checked. So I guess a weaker conjecture than the main one here is:
Can one disprove the possibility that the numerators of the remainders in an odd greedy instance look like 5,6,7,8,.........all the way to infinity?
Eppstein is working on a Mathematica package that incorporates a variety of methods. David Bailey (and I) continue to wonder about 5/5809's behavior under odd greedy. His program checks to 60,000,000 digits, but it did not halt. So, if this halts, it leads to numbers having more than 60,000,000 digits.
Eppstein's package has no trouble finding reps. of 5/5809 such as: 1/897 + 1/6739 + 1/20217 and 1/2051 + 1/2925 + 1/5567 + 1/5985 + 1/7325. Eppstein adds that his small max-denominator result reported in previous mailing is provably optimal. Readers interested in his general-purpose Egyptian fractions package should contact him: eppstein@euclid.ics.uci.edu.
NEW! David Eppstein, using modular reduction (continually reduce the denominator modulo, say, 30!) was able to prove that the sequence does indeed halt, and that the numerators of the remainders look like 5, 6, 7, ..., 29, 30, 1. (David actually used the modulus 37943838567204570000 = 30!/224·310·53·7.) This is very clever and completely avoids the ridiculously large numbers one gets without the reduction. Bailey got up to 60,000,000 digits in the 24th denominator, and then was forced to stop. But now we now that a few more steps does indeed lead to termination in this one case. Nice work, David.
[The following is an email message from David Eppstein to Stan Wagon outlining his results for 3/179:]Jeff Erickson forwarded me your above-titled message on odd Egyptian fraction representations of 3/179. You asked to be sent any solutions.
As I believe you know, I have a large collection of algorithms for constructing Egyptian fractions, published in Mathematica in Educ. & Res., and online at http://www.ics.uci.edu/~eppstein/numth/egypt/. Most of these methods produce some even denominators, but a few do not. (Beware, I probably introduced some typos transferring these from my Mac to my Sun.)
EgyptOddGreedy[3/179] didn't terminate in a reasonable amount of time. I assume this is why you chose this particular fraction to ask about...
The proofs I know of that odd representations exist are I think pretty similar to the method I implemented as EgyptRemainder, which takes as a second argument a "powerful" number (with lots of divisors so that there are lots of ways to form sums of divisors). If the powerful number is odd, you get odd representations, modulo some recombination that happens because of possible repeated terms. EgyptRemainder[3/179,3*3*3*5*5*7] yielded the following:
1/105 + 1/189 + 1/525 + 1/33831 + 1/93795EgyptShort[3/179,3], a close-to-brute-force search for representations with few terms (the second argument is the number of terms) produced a number of three-term representations, among them the odd
1/105 + 1/189 + 1/525 + 1/31325 + 1/120825
1/105 + 1/175 + 1/675 + 1/33831 + 1/93795
1/105 + 1/175 + 1/675 + 1/31325 + 1/120825
1/75 + 1/525 + 1/675 + 1/33831 + 1/93795
1/75 + 1/525 + 1/675 + 1/31325 + 1/120825
1/75 + 1/315 + 1/4725 + 1/33831 + 1/93795
1/75 + 1/315 + 1/4725 + 1/31325 + 1/120825
1/63 + 1/1575 + 1/4725 + 1/33831 + 1/93795
1/63 + 1/1575 + 1/4725 + 1/31325 + 1/1208251/61 + 1/2745 + 1/491355These are therefore the only odd three-term representations. The last of these is particularly succinct. There is only one two-term representation of 3/179, not odd.
1/63 + 1/1253 + 1/11277
1/63 + 1/1611 + 1/3759A small modification of EgyptSmallMult (another brute force method, which combines small multiples of the original fraction in order to get something that differs from the input by a fraction not divisible by the original denominator) shows that
3/179 = 1/895 + 1/1611 + 1/1969 + 1/2685 + 7/495,and that any other set of odd unit fractions having a difference from 3/179 that is not itself a multiple of 1/179 must include a higher denominator. Calling EgyptShort on 7/495 produces the representations
3/179 = 1/179 + 1/537 + 1/895 + 1/1253 + 1/2327 + 1/2685 + 3/455,1/895 + 1/1611 + 1/1969 + 1/2685 + 1/77 + 1/1485 + 1/2079which have the minimum max denominator (2685) of any odd representation of 3/179. Unless I missed one in going through the results, all other representations with the same max denominator have more terms.
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/77 + 1/1575 + 1/1925
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/77 + 1/1683 + 1/1785
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/891 + 1/1485
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/935 + 1/1377
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/561 + 1/1683
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/693 + 1/1071
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/81 + 1/765 + 1/935
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/87 + 1/495 + 1/1595
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/91 + 1/585 + 1/693
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/95 + 1/495 + 1/627
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/275 + 1/2475
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/285 + 1/1881
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/297 + 1/1485
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/315 + 1/1155
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/385 + 1/693
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/99 + 1/429 + 1/585
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/105 + 1/315 + 1/693
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/105 + 1/385 + 1/495
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/117 + 1/195 + 1/2145
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/117 + 1/209 + 1/1235
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/117 + 1/221 + 1/935
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/135 + 1/165 + 1/1485
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/135 + 1/189 + 1/693
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/135 + 1/209 + 1/513
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/143 + 1/195 + 1/495
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/165 + 1/225 + 1/275
1/895 + 1/1611 + 1/1969 + 1/2685 + 1/171 + 1/209 + 1/285-- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Jeff Erickson
(jeffe@cs.duke.edu)
17 Dec 97