Egyptian Fracs: Algorithm for Minimizing Terms/Denominator

[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?

 

[HallsofIvy]

My hunch would be the "greedy" algorithm. Given rational x₁, let n be the smallest integer such that 1/n< x₁. Now repeat the process with x₂= x₁- 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?

 

[shmoe]

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

https://www.physicsforums.com/showthread.php?t=119708&highlight=egyptian


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.

 

[HallsofIvy]

Thanks, shmoe, I was wondering about that.

I have edited my post so it makes sense now!

 

[Dragonfall]

Thanks for the help.