About egyptian fractions (from POWT-L)
Olivier Gerard
ogerard at ext.jussieu.fr
Wed Mar 4 21:19:58 CET 1998
Neil's proposition may evoke things to
recipents of the Problem of the Week mailing list.
=46or your information, I forward here some of Stan Wagon
postings about this. I hope Stan won't mind and he is
heartily invited to join us at seqfan. Sorry for
seqfan members who are linked to the POTW-L and could
see that as cross-posting.
I have appended the closing-banner of POTW-L so that
people wanting to do so can join it.
Good reading
Olivier
- ------------------------------------
Problem 848 An Odd Egyptian Puzzle
- ------------------------------------
It is known that any fraction with an odd denominator is a sum
of reciprocals of distinct odd integers. For example,
35 1 1 1
--- =3D - + -- + ----- .
179 7 19 23807
=46ind such an expression for 3/179.
BACKGROUND: Such sums (with no odd restriction) are often
called Egyptian fractions. One can attempt to use a "greedy"
algorithm on this sort of problem. But, despite the fact that,
as proved by Fibonacci, the greedy algorithm for unrestricted
Egyptian fractions always halts, it is a famous unsolved
problem whether the "odd greedy algorithm for Egyptian
fractions" always halts. This open problem is discussed in Klee
& Wagon, "Elementary Unsolved Problems in Plane Geometry and
Number Theory" (MAA). That book, by the way, appeared in a
German translation this week (Birkhauser).
Date: Thu, 06 Nov 1997 13:57:46 -0500 (CDT)
=46rom: Stan Wagon <WAGON at macalester.edu>
Subject: not a problem
To: problems:;
- -------------
NOT A PROBLEM
- -------------
Problem 848 generated so much interest that I am sending out this general
update. #849 will appear on schedule next week.
Please note that if a PoW message bounces I remove the offending address fro=
m
the list. Maintaining this list is in fact a lot of work, but interactions l=
ike
those that occurred this week make it extremely worthwhile!
This note contains comments on the Egyptian fraction odd denominator=
problem, a
few misc. general messages, and then some Mathematica code at the end.
- ---------------------------------------------------------------
A reader, who shall remain anonymous, said: "I do not think the 3/179 proble=
m
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, n odd, is a sum of distinct =
odd
unit fractions.
=46amous unsolved problem (see [Guy, Unsolved Problems in Number Theory,
Springer; or Klee & Wagon, Old and New Unsolved Problems in Plane Geometry a=
nd
Number Theory, MAA]: Does the odd greedy algorithm for getting a representat=
ion
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 od=
d
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, beginni=
ng
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), are
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1
Quite 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 b=
e
the case that Brown's solution is the simplest 3-term representation there i=
s.
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 immortali=
zed
on the Rhind papyrus, and Milo Gardner has made an extensive investigation.
Contact him for details at gardnerm at ecs.csus.edu.
Eppstein also found that 3/179 =3D
1/171 + 1/209 + 1/285 + 1/895 + 1/1611 + 1/1969 + 1/2685
which might be the smallest max-denominator.
Eppstein's home page has misc. Egyptian fraction stuff
(http://www.ics.uci.edu/~eppstein/numth/egypt/) and his article in Mathemati=
ca
in Education and Research [vol 4, no. 2, 1995, pp 5-15] discusses Mathematic=
a
implementations of a variety of algorithms. I guess I should throw my own co=
de
down. I append it later. 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. Code from revision of =
my
book, Mathematica in Action (Springer).
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 fam=
ous
conjectures in this area:
4/n has a 3-term representation. (Erdos and Straus)
5/n has a 3-term represntation (Sierpinski)
Richard Guy (Calgary) observes: 3/(6n+1) =3D 1/(2n+1) + 1/(2n+1)(4n+1) +
1/(4n+1)(6n+1), and some others along these lines.
David Bailey (NASA Ames), using customized high-precision arithmetic on an S=
GI
work station and aware of my desire to "stump" the odd greedy algorithm, fou=
nd
the following monster:
3/2879: the odd greedy rep'n has 21 terms; the last term has 3,018,195 digit=
s;
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, 1
I believe with this computation David gets the record for the largest Egypti=
an
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-denominat=
or.
It would be nice to have some heuristics to predict where the bad examples f=
or
the odd greedy algorithm are. In particular, I would like one that stumps Da=
vid
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-dig=
it
precision. He gets:
1/163 + 1/1125979 + [21 terms omitted] + 1/s + ...
where the integer s is approximately 6.875 x 10^12565952.
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 th=
e
algorithm halts. This is very nice indeed.
Of course, I have no doubt that nice rep'ns exist. The issue is that oidd
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?
- ------------------------------------------------------------
Mathematica Code for odd greedy algorithm. Note the options, which are usefu=
l
in large computations.
- ------------------------------------------------------------
OddGreedyEF::pastmx =3D "The maximum size of a term has been exceeded, so th=
e
result is only partial.";
OddGreedyEF::usage =3D "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 =3D "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 =3D "PrintPartial results is an option to OddGree=
dyEF
that causes the terms, and perhaps the remainder-numerators to be shown as t=
he
computation proceeds.";
ShowNumerators::usage =3D "ShowNumerators is an option to OddGreedyEF that c=
auses
the output to include the numerators of the remainders.";
Options[OddGreedyEF] =3D {ShowNumerators -> False,
PrintPartialResults -> False, MaxTerm -> =B0};
OddGreedyEF[0, oldMax_, opts___] :=3D {{}, {}}
OddGreedyEF[q_, oldMax_Integer:1, opts___Rule] :=3D Module[
{m =3D Max[oldMax + 2, Ceiling[1/q]]},
{numQ, prQ, mx} =3D
{ShowNumerators, PrintPartialResults, MaxTerm} /.
{opts} /. Options[OddGreedyEF];
If[oldMax =3D=3D 1, nums =3D {}];
If[!numQ && oldMax =3D=3D 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]]
- ----------------------------------------------------------------------------=
- --
This was the Problem of the Week from Stan Wagon at Macalester College in St=
=2E
Paul, Minnesota <<wagon at macalester.edu>>. This Macalester tradition was
started by the late Joe Konhauser in 1968 and has continued unbroken since
then.
These problems are intended for our undergraduates. I do not
necessarily wish to receive e-solutions unless:
(a) you have an interesting nonstandard approach to a solution;
(b) you have a variation or extension that might be worthy of
dissemination; or
(c) you have information about the history of the problem. Of
course, I encourage your problem suggestions.
PROBLEM ARCHIVES:
1. There is an electronic archive of recent Problems of Week at
http://www.cs.duke.edu/~jeffe/wagon/
2. "Which Way Did the Bicycle Go?" by Joseph Konhauser, Dan
Velleman, and Stan Wagon is available from the MAA. This book
consists of 191 problems and solutions selected from the Problems
of the Week at Macalester College from 1968 to 1995.
Contact: 800-331-1622 or http://www.maa.org
POW SUBSCRIPTIONS:
One can subscribe to the list by sending a message
containing only the line:
SUBSCRIBE POTW-L
to << mailserv at macalester.edu >>.
To change your address, use preceding method for the new address,
and send me an e-mail asking me to remove your old address.
To simply unsubscribe, send a message to << mailserv at macalester.edu >>
from the account to be unsubscribed and containing the body:
UNSUBSCRIBE POTW-L
More information about the SeqFan
mailing list