Apparently the greedy Egyptian fraction algorithm appeared in Fibonacci’s Liber Abaci from 1202! This and a wealth of other things on EFs are here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html <http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html> - Cris
On Dec 13, 2018, at 7:15 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Cris Moore <moore@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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun