# Homework Help: Egyptian Fractions

1. Sep 27, 2006

### Dragonfall

Is there an algorithm which can convert any rational number to a sum of distinct unit fractions which minimizes the number of terms or the largest denominator?

2. Sep 27, 2006

### HallsofIvy

My hunch would be the "greedy" algoritm. Given rational x1, let n be the smallest integer such that 1/n< x1. Now repeat the process with x2= x1- 1/n.

For example to find the unit fractions for 13/17:
It is clear that 1/2< 13/17 so our first unit fraction is 1/2. 13/17- 1/2= 26/34- 17/34= 9/34. 1/3> 9/34 but 1/4< 9/34 so our second unit fraction is 1/4. 9/34- 1/4= 18/68- 17/68= 1/68 which is itself a unit fraction.
13/17= 1/2+ 1/4+ 1/68.

Is it necessary to include "which minimizes the number of terms or the largest denominator"? Isn't decomposition into unit fractions unique?

Last edited by a moderator: Sep 27, 2006
3. Sep 27, 2006

### shmoe

The decomposition is not at all unique. 1/2=1/3+1/6 for example. See the algorithm described in

The greedy algorithm can fail to give the representation with the least number of terms and smallest denominators. See

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html#Fibgreedy

I'm not sure of the algorithm that finds the shortest, but they have a calculator on that page that claims to, so that page is probably a good place to start.

Last edited by a moderator: Apr 22, 2017
4. Sep 27, 2006

### HallsofIvy

Thanks, shmoe, I was wondering about that.

I have edited my post so it makes sense now!

5. Sep 27, 2006

### Dragonfall

Thanks for the help.