Cris Moore <moore(a)santafe.edu> wrote:
> But it?s a lovely exercise that the greedy algorithm for Egyptian
> fractions ? that is, subtract the largest reciprocal ? terminates
> for any rational number between 0 and 1. There?s an inductive proof,
> but the nature of the induction is surprising.
Found it! The numerator always decreases. For instance for 4/97,
whose GEF is 1/25 + 1/809 + 1/980913 + 1/1924379646225, the remainders
are 4/97, 3/2425, 2/1961825, and 1/1924379646225.
(My first thought was that the denominators increase so quickly that
the partial sums are too close to rationals, thus proving that any
non-terminating GEF must be irrational. There were just two minor
problems. One is that any such proof would probably also prove that
all non-terminating GEFs must be transcendental, which is absurd,
since all algebraic irrationals have a non-terminating GEF. The
other is that the inverse Sylvester sequence (1/A000058) is a
non-terminating GEF that converges to 1.)
It's also true for any rational number between 0 and 2. For instance
for 19/10, whose GEF is 1/1 + 1/2 + 1/3 + 1/15, the remainders are
19/10, 9/10, 2/5, and 1/15.
It's not true for most larger rationals, but I think I can extend the
proof to cover them anyway.
I've read that it's not known whether GEFs constrained to only use
odd denominators will terminate for every rational with an odd
denominator. (It's easy to see that none will terminate for any
rational with (in simplest form) an even denominator.) There's no
obvious pattern in the numerators of the remainders. For instance
2/3, whose OGEF is 1/3 + 1/5 + 1/9 + 1/45 has remainders of 2/3, 1/3,
2/15, and 1/45. Apparently nobody has yet found any rational with an
odd denominator known not to have a terminating OGEF.
