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

    HallsofIvy

    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

    shmoe

    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

    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.
     
    Last edited by a moderator: Apr 22, 2017
  5. Sep 27, 2006 #4

    HallsofIvy

    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