Sage code for unit fraction representation

Here comes a sage code for computing the unit fraction representation of any fraction less than 1. For details about the algorithm see my previous blog entry.

def find_d(a, b):
   """find an appropriate unit fraction"""
   d=1
   while 1/d>a/b:
      d+=1
   return d

#input numerator and denominator separately
a=raw_input("Please insert numerator:")
b=raw_input("Please insert denominator:")
a=float(a)
b=float(b)

print "Unit fraction representation of %i/%i"%(a,b)

d=find_d(a,b)
print "1: ", 1/d  #first unit fraction

i=2
while (a*d-b <> 1) & (a*d-b <> 0) :
   a=a*d-b
   b=b*d
   d=find_d(a,b)
   print "%i: "%i, 1/d
   i+=1

#last unit fraction
if (a*d-b <> 0) :
   print "%i: %i/%i"%(i,(a*d-b),(b*d)) 

Unit fraction representation

While reading the biography of Paul Erdős (The man who loved only numbers by Paul Hoffman) I accidentally bumped into the following problem: Is it possible to represent a fraction as a sum of unit fractions if all denominators have to be distinct?

Unit fractions are fractions that are the recopricals of positive integers, like or

Leonardo Fibonacci positively answered it in 1202: any ordinary fraction can be expressed as a sum of unit fractions in infinitely many different ways. The key to this statement is the identity

Applying this identity again and again, a sum of unit fractions can be continously expanded. For example:

When constructing unit fractions this way, one can follow the so-called greedy procedure.

Greedy procedure of :

1. if is a unit fraction then the process is over (nothing has to be done)
2. let be the largest unit fraction less than Such a unit fraction always exists and is unique.
3. If is a unit fraction than the process is over. In this case , implying that has to be a different unit fraction than
4. If is not a unit fraction than choose the largest unit fraction less than
5. Apply step 3 to

One question remained open: does the procedure allways end in finite many steps? And the answer is yes because the numerator of the remaining part is decremented in every step and thus reaches 1 sooner or later…

Let is the largest unit fraction in the n-th step less than . Let such that: and

Then the following equations hold:

  (1)

  (2)

Equation (1) implies that the numerator decreases if

From the inequality (2):

Substracting from both sides yields:

(3)

And (3) is exactly what we wanted to show (q.e.d.).