As far as I know, it is still a case of brute force to find the minimal Egyptian fraction format. David Epstein has done a lot of excellent work on the algorithmic side, and probably more than you want to know about it can be found at his website https://www.ics.uci.edu/~eppstein/numth/egypt/intro.html At a higher level, he has a whole bunch more information of Egyptian fractions at https://www.ics.uci.edu/~eppstein/numth/egypt/ Steve On Dec 15, 2018, at 12:31 PM, Cris Moore <moore@santafe.edu<mailto:moore@santafe.edu>> wrote: Is anything known about the computational complexity of finding the minimal Egyptian fraction (either minimizing the number of terms or the total length of the denominators)? - Cris On Dec 13, 2018, at 7:15 PM, Keith F. Lynch <kfl@KeithLynch.net<mailto:kfl@KeithLynch.net>> wrote: Cris Moore <moore@santafe.edu<mailto: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<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...