
Re: unitary (Egyptian) fractions
Posted:
Mar 20, 2000 11:26 PM


> I dusted off some old Egyptian fraction code I wrote a couple of years > ago. It uses Common Lisp's exact integer arithmetic, so roundoff is > not an issue. I verified that all fractions up to 732/733 have > sixterm representations and that 732/733 requires seven terms.
> It took about 13 hours on a 296 Mhz Ultra. If a mips is a > Mhz, that's almost half a mipsyear. I don't how much of the > remaining speed difference is due to the programming language/system > and how much is due to the algorithm.
> By the way, I found that 732/733 has 2771 different seventerm > representations. The largest denominator appears in the > representation (2305193137933140 33397845 4484 45 7 3 2). The > smallest maximum denominator appears in (26388 20524 7330 45 7 3 2).
It turns out that, if you don't want all representations, just the one minimizing the max denominator, you can find it rather more quickly:
Timing[EgyptianFraction[732/733,Method>{SmallMultiples,Greedy},MaxTerms>7]]
{ 1774.38333333333346 Second, 1/2 + 1/3 + 1/7 + 1/45 + 1/7330 + 1/20524 + 1/26388 }
So, about a half hour, on a 200MHz PowerPC 603e (I think quite a lot less powerful than your Ultra). Still not as fast as I'd like, though...  David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

