The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: unitary (Egyptian) fractions
Replies: 17   Last Post: Mar 31, 2000 6:38 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
eppstein@euclid.ics.uci.edu

Posts: 128
Registered: 12/8/04
Re: unitary (Egyptian) fractions
Posted: Mar 20, 2000 11:26 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



> 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
> six-term 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 mips-year. 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 seven-term
> 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/







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.