Date: Mar 27, 2000 1:18 AM
Subject: Re: unitary (Egyptian) fractions

"r3769" <> 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) is
much slower than sometimes finding one solution (which yours does),
finding one solution whenever one exists, or even finding the best
solution (e.g. with best = min max denominator).

Looking at your program, it seems it simply applies the greedy algorithm
to the fractions m/n - 1/x for 100000 choices of x, stops if it gets an
expansion with few enough terms, and otherwise gives up. It is clear
that this is fast (takes at most 100000 iterations for any number) and
works for many values of m/n. I suspect though that there are some short
expansions you will never find even if you change the 100000 to your
favorite larger number, because they require more than one non-greedy

Dan's code (and some of my code and probably a bunch of other people's
code) on the other hand does a recursive backtracking search for
solutions -- think of a program like yours but with seven nested loops
to try multiple choices not only for D0 but also D1, D2, etc -- so it's
guaranteed not to miss a solution. Of course there are tricks to speed
it up, like choosing the number of iterations more intelligently,
backtracking when you get a fraction that's going to require too many
more terms, or doing something involving factoring when you get down to
only two terms, but it will still be slower than code like yours.

Your program has been useful, for finding examples of small fractions
which require many terms and for quickly eliminating many other possible
examples of small fractions. So don't think you have a bad algorithm for
those sorts of tasks, although you might be better off reducing the
100000 to something much smaller (100 or 1000?) and switching to a more
powerful method for the values of m/n on which that fails.

I'm also guilty (in a couple of earlier messages in this thread) of
comparing my speed to Dan's for code that does different things. But
this sort of comparison isn't really fair, because it paints Dan as a
bad programmer which is I think not true -- he wants more out of his
program and is willing to put in the CPU time to get it.
David Eppstein UC Irvine Dept. of Information & Computer Science