Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Egyptian Fractions

  1. Sep 27, 2006 #1
    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. jcsd
  3. Sep 27, 2006 #2


    User Avatar
    Science Advisor

    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
  4. Sep 27, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    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


    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
  5. Sep 27, 2006 #4


    User Avatar
    Science Advisor

    Thanks, shmoe, I was wondering about that.

    I have edited my post so it makes sense now!
  6. Sep 27, 2006 #5
    Thanks for the help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook