Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Puzzles
Middle School Fractions
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search