```Date: Mar 27, 2000 1:18 AM
Author: eppstein@euclid.ics.uci.edu
Subject: Re: unitary (Egyptian) fractions

"r3769" <r3769@calweb.com> writes:> Dan Hoey wrote >> >It took about 13 hours on a 296 Mhz Ultra.> > It could be the algorithm.   For example, the following UBASIC program> verifies all a/b [2<=b<=733, 1<=a<b, (a,b)=1] except> {429/431,562/563,640/643,631/647,653/659,732/733} have a six-term (or less)> expansion in less than 4 MINUTES on my PC.As Dan wrote earlier, listing all solutions (which his code does) ismuch slower than sometimes finding one solution (which yours does),finding one solution whenever one exists, or even finding the bestsolution (e.g. with best = min max denominator).Looking at your program, it seems it simply applies the greedy algorithmto the fractions m/n - 1/x for 100000 choices of x, stops if it gets anexpansion with few enough terms, and otherwise gives up.  It is clearthat this is fast (takes at most 100000 iterations for any number) andworks for many values of m/n. I suspect though that there are some shortexpansions you will never find even if you change the 100000 to yourfavorite larger number, because they require more than one non-greedychoice.Dan's code (and some of my code and probably a bunch of other people'scode) on the other hand does a recursive backtracking search forsolutions -- think of a program like yours but with seven nested loopsto try multiple choices not only for D0 but also D1, D2, etc -- so it'sguaranteed not to miss a solution.  Of course there are tricks to speedit up, like choosing the number of iterations more intelligently,backtracking when you get a fraction that's going to require too manymore terms, or doing something involving factoring when you get down toonly two terms, but it will still be slower than code like yours.Your program has been useful, for finding examples of small fractionswhich require many terms and for quickly eliminating many other possibleexamples of small fractions. So don't think you have a bad algorithm forthose sorts of tasks, although you might be better off reducing the100000 to something much smaller (100 or 1000?) and switching to a morepowerful method for the values of m/n on which that fails.I'm also guilty (in a couple of earlier messages in this thread) ofcomparing my speed to Dan's for code that does different things.  Butthis sort of comparison isn't really fair, because it paints Dan as abad programmer which is I think not true -- he wants more out of hisprogram and is willing to put in the CPU time to get it.-- David Eppstein       UC Irvine Dept. of Information & Computer Scienceeppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
```