Egyptian Fractions

When ancient Egyptians wrote fractions they were only able to use ones of the form 1/a, called unit fractions. An Egyptian wanting to write the fraction b/c, where b was not 1, had to write it as the sum of (different) unit fractions. All fractions b/c (b < c) can be written as an Egyptian fraction.

For example, the fraction 5/6 was written as 1/2 + 1/3, and 6/7 was written as 1/2 + 1/3 + 1/42. Egyptian fractions are not necessarily unique: 6/7 can also be written as 1/2 + 1/4 + 1/14 + 1/28. Since the unit fractions must be different, 2/3 can be written as 1/2 + 1/6, but not 1/3 + 1/3.

An Egyptian fraction representing b/c is 'minimal' if it uses the smallest number of unit fractions possible. An Egyptian fraction is 'optimal' if it is minimal, and the smallest unit fraction is as large as possible. There may be several minimal and several optimal Egyptian fractions for a given b/c.

For example 19/45 cannot be represented as the sum of two unit fractions, but there are 5 ways of representing it as the sum of 3 unit fractions: 1/3 + 1/12 + 1/180, 1/3 + 1/15 + 1/45, 1/3 + 1/18 + 1/30, 1/4 + 1/6 + 1/180 and 1/5 + 1/6 + 1/18. These five Egyptian fractions are all minimal. Only 1/5 + 1/6 + 1/18 is optimal, since 1/18 is larger than 1/30, 1/45 and 1/180.

• Write a program that inputs two numbers a and b, and calculates an Egyptian fraction representing a/b with no more than a unit fractions. You will only be given fractions with 0 < a < b < 1000. Your program should then output the denominators (bottom parts) of the unit fractions.

Sample run
Numerator: 19
Denominator: 45
5 6 18

There will be ten tests. For each test, if there exists an optimal solution which is the sum of 4 (or fewer) unit fractions, more points will be given for outputting an optimal solution.

• What fractions do the following Egyptian fractions represent?
  (i) 1/8 + 1/56
  (ii) 1/2 + 1/4 + 1/8 + 1/16 + 1/32
• Do there exist any fractions for which there is a unique Egyptian fraction?
• How many different valued fractions (a/b) are there if 0 < a < b < 1000?
  [Hint : Remember, for example, that 1/2 and 2/4 have the same value.]

Solution page for Egyptian Fractions