Date: Mar 20, 2000 9:04 PM
Author: Dan Hoey
Subject: Re: unitary (Egyptian) fractions



Hugo van der Sanden wrote:

> Prompted by a recent reference to the section (D11) on Egyptian
> fractions in Guy's 'Unsolved Problems in Number Theory', I noticed
> mention of this problem (paraphrased):


> Order the rationals a/b, 0 < a/b < 1, (a, b) = 1, by increasing a+b
> and then by increasing a: 1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5, 3/4 ...


> What is the earliest such rational that cannot be expressed as the
> sum of n unit fractions?


I'm sure you mean n _distinct_ unit fractions.

> I was surprised that so few results were known: 2/3, 4/5, 8/11, 16/17,
> 77/79 cannot be expressed as the sum of 1, 2, 3, 4, 5 unit fractions
> respectively. So I write a simplistic perl program, which has found
> (after just over a mips-year of work) that 732/733 is the first in the
> list that cannot be expressed as the sum of 6 unit fractions.


> Since this program exercises perl beyond the limits of its integer
> accuracy, I cannot guarantee the result - can anyone confirm it for me?


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).

Dan Hoey <haoyuep@aol.com> Posted and e-mailed