Egyptian Fractions

Date: 06/11/2001 at 07:33:18
From: Andrew
Subject: Egyptian Fractions

I just got a problem solving a puzzle for maths that involves Egyptian 
fractions, e.g. 2/7 = 1/4 + 1/28.

The Egyptians wrote all their fractions as a sum of different 
fractions with a numerator of 1. I need to find a way to work out what 
fractions should be added together to get the answer I require. 

I worked out that in the example 2/7 = 1/4 + 1/28, 
2/(2i+1) = 1/(i+1) + 1/x, and that x is equal to 7 multiplied by 4.  
This rule only works, however, if the numerator of the number you are 
working out is 2, and even then only sometimes.  

Any suggestions?

Date: 06/11/2001 at 15:22:46
From: Doctor Rob
Subject: Re: Egyptian Fractions

Thanks for writing to Ask Dr. Math, Andrew.

There is something called the Greedy Algorithm that always works.
Suppose you are trying to write a/b as such a sum. Take for your first 
fraction 1/n, where n is the smallest integer greater than or equal to 
b/a. Then write a/b - 1/n = (n*a-b)/(b*n) = a'/b'. Repeat this 
procedure until a'/b' = 0, and stop.

Example:

   a/b = 38/199, b/a = 199/38 = 5 + 9/38,

so n = 6.  Then

   38/199 - 1/6 = (228-199)/1194 = 29/1194.

Repeat with 29/1194.

   1194/29 = 41 + 5/29,

so n = 42 is next.  Then

   29/1194 - 1/42 = 2/4179.

Repeat with 2/4179.

   4179/2 = 2089 + 1/2,

so n = 2090 is next.  Then

   2/4179 - 1/2090 = 1/8734110.

Putting this all together, you get

   38/199 = 1/6 + 1/42 + 1/2090 + 1/8734110.

This always works, but it doesn't always give you the fewest fractions
or the smallest denominators.

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