1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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


    User Avatar
    Staff Emeritus
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Egyptian Fractions
  1. Partial fractions (Replies: 2)

  2. Derivative of a fraction (Replies: 10)