Unit Fractions and the Greedy Algorithm

Date: 12/27/2000 at 07:28:12
From: Tok Foon
Subject: Express 2000/2001 using unit fractions

Dear Dr. Math,

I've found many ways to express 1999/2000 as a sum of distinct 
positive unit fractions. For example, two of the many possible ways 
are 1/10 + 1/50 + 1/250 + 1/2000 and 1/10 + 1/50 + 1/400 + 1/500.

I tried, but don't seem to be able to express 2000/2001 as a sum of 
distinct positive unit fractions. I'm beginning to wonder if there is 
any solution.

Hope someone can help.

Date: 12/27/2000 at 11:01:55
From: Doctor Rob
Subject: Re: Express 2000/2001 using unit fractions

Thanks for writing to Ask Dr. Math, Tok Foon.

Sorry, but the two sums you gave add up to 249/2000, not to 1999/2000. 
 You apparently left off 1/2 + 1/4 + 1/8 from the front of each sum.

What you ask can always be done. One way is to use the Greedy 
Algorithm. For the first fraction, choose the largest unit fraction 
not greater than the target number. Subtract that, and repeat. This 
method will always terminate.

For example, for 1999/2000, the largest unit fraction not greater than 
it is 1/2. Then:

     1999/2000 - 1/2 = 999/2000

Next, the largest unit fraction not greater than 999/2000 is 1/3, and:

      999/2000 - 1/3 = 997/6000

Continuing in this way, you get:

     1999/2000 = 1/2 + 1/3 + 1/7 + 1/43 + 1/18619 + 1/781998000

This won't always give you the shortest sum, or the one with the 
smallest denominators, but it will always work.

There are always infinitely many ways to write any fraction as a sum 
of distinct unit fractions. For example, you can always replace the 
smallest fraction in the sum, 1/A, by

     1/A = 1/(2*A) + 1/(3*A) + 1/(6*A)

and get a different, larger set of fractions with the same sum.

Now try 2000/2001 again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/