From: David Eppstein
Subject: Re: Egyptian Fractions question
Date: Wed, 13 Sep 2000 08:46:41 -0700
Newsgroups: sci.math
Summary: [missing]
In article <8pnmk3$mht$1@news.netvision.net.il>, "Yakov Hoch"
wrote:
> I've been checking out algorithms for producing Egyptian fractions
> representations of rational numbers. However, I couldn't find any proof that
> these algorithms will always terminate. Any help would be appreciated.
Different algorithms have different proofs. My web notebook "Algorithms
for Egyptian Fractions"
(http://www.ics.uci.edu/~eppstein/numth/egypt/intro.html)
certainly has some proof ideas, but usually very informally presented,
for instance early on in greed.html it talks about the denominator becoming
smaller at each step (similar to the proof someone else already posted
about the numerator getting smaller for the usual greedy method).
There is a more explicit discussion about termination in conflict.html.
The famous "odd greedy" open problem about Egyptian fractions is exactly a
question of whether a certain algorithm terminates, so these questions can
be very difficult. (The algorithm is, given x/y with y odd, repeatedly
subtract the largest possible odd unit fraction.)
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/