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/