[BIO97 Logo] The British Informatics Olympiad
Sponsored by Data Connection.
[Data Connection logo]
-----

The 1997 British Informatics Olympiad Round One

Question 3

Question 3
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.

3 (a)
[23 marks]
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.  
  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 marks will be given for outputting an optimal solution.

Sample run
Numerator: 19
Denominator: 45
5 6 18

  No unit fraction will need to be smaller than 1/32000. [You can still output denominators greater than 32000, so long as they are no more than 8 digits long.]  
3 (b)
[2 marks]
What fractions do the following Egyptian fractions represent?
(i) 1/8 + 1/56
(ii) 1/2 + 1/4 + 1/8 + 1/16 + 1/32
3 (c)
[5 marks]
Do there exist any fractions for which there is a unique Egyptian fraction?
3 (d)
[5 marks]
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.]

The British Informatics Olympiad - BIO'97 exam - BIO'98 sample paper