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