The British Informatics
OlympiadSponsored by Data Connection. |

Question 3 |

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. No unit fraction
will need to be smaller than 1/32000.*

There are many ways to solve this question. A simple solution
is possible if we assume that we will never need more than 4 unit
fractions and no denominator will exceed 32000. A first approach
to the problem could be as follows. Check if the solution is
already Egyptian (which will be the case if *a* divides *b*).
Otherwise, try 2, then 3, then 4 combinations of unit fractions.
Constraints can be found to limit the number of combinations that
need to be investigated, such as making them increase and
stopping searching when no solution is possible.

This approach solves the problem quickly if a solution with 2 unit fractions exists - needing to investigate fewer than 1000 numbers. The search space increases over a thousand times for each additional unit fraction - making it feasible to search for 3 (of the order of millions of combinations) but practically impossible to find solutions requiring 4 unit fractions in the two minutes available for programs to run.

The search can be speeded up considerably. Let the solution be (C1+...Cn)/D, where each Ci divides D. It can be assumed that D is a multiple of B, and each Ci is a distinct divisor of D. This can result in a very much smaller search space, particularly if B is a large prime number. An upper limit on D might be as large as A*B, so valid or optimal solutions may be missed by, for example, constraining D<=32000; nevertheless, this method makes the search method very much faster.

Search is used in the example solution program for 3(a), which can be run in a Java-enabled browser. It was also the method chosen by Stephen Williams, who got the highest mark (20 out of 23) for this question, and you can view his program q3a.pas or download a zip archive containing a PC/DOS executable.

A rather different approach can find solutions very quickly,
but does not guarantee that they will be optimal. *a*/*b*
can be written as the sum of *a* unit fractions of 1/*b*.
This is not an Egyptian fraction (the unit fractions must be
distinct), but it can be converted into an Egyptian fraction
using these rules:

- common factors: if some
*c*<=*a*divides*b*,*c*unit fractions can be written as 1/(*b*/*c*) - splitting: 2/
*b*, where*b*is odd, can be written as 1/*c*+ 1/*d*where*c*=(*b*+*n*)/2 and*d*=*b*(*b*+*n*)/2*n*and*n*is odd (at least one solution,*n*=1, exists).

Repeated application of these rules will reduce *a*/*b*
to an Egyptian fraction. However, for large *b*, the unit
fractions may be very small (potentially to small to be
represented as the reciprocal of a 32-bit integer), and there may
be many (there will be no more than *a*). This provides a
fast, but non-optimal solution.

**Marking**

All ten tests in this section have multiple solutions. For each test only the optimal solutions are given. For the first seven tests, the program gets two marks for finding these optimal solutions and one mark for a non-optimal solution. (Examples of likely non-optimal solutions to Tests 5, 6 and 7 are given in brackets.)

If alternative solutions are produced they should be checked by calculator. A solution to the input "a b" is valid if a/b is equal to the sum of the reciprocals of the numbers output. Additionally, the numbers output must all be different, and should have no more than 8 digits.

Mark tests 1-7 as follows:

[2] If the answer given is one of the optimal solutions.

[1] If the answer given is valid but not optimal.

[2] Test 1: 1 20 20 [2] Test 2: 36 612 17 [2] Test 3: 2 15 12 20 [2] Test 4: 2 37 19 703 [2] Test 5: 27 441 28 49 196 (17 417 347361) [2] Test 6: 4 109 30 545 654 (28 1018 1553468) [2] Test 7: 59 211 4 36 633 3798 6 9 633 3798 (4 34 4783 68626484)

For the final three tests **any valid solution
**scores all [3] marks. An additional non-optimal solution is
given for test 8, and test 10 has four equally valid optimal
solutions. If other output is produced, use a calculator to check
that it is a valid solution to within rounding error.

[3] Test 8: 101 103 2 3 7 238 5253 (2 3 7 228 164388) [3] Test 9: 907 911 2 4 5 22 10021 18220 [3] Test 10: 523 547 2 3 9 90 2735 4923 2 3 10 45 2735 4923 2 3 15 18 2735 4923 2 4 5 180 2735 4923

3 (b) [2 marks] *What fractions do the
following Egyptian fractions represent?*

(i) 1/8 + 1/56 = 1/7 [1 mark]

(ii) 1/2 + 1/4 + 1/8 + 1/16 + 1/32 = 31/32 [1 mark].

3 (c) [5 marks] *Do there exist any
fractions for which there is a unique Egyptian fraction?*

A total of five marks may be obtained by making the following points.

[1] No.

[1] All fractions (b/c) can be written as an Egyptian fraction.

[1] Every unit fraction can be written as an Egyptian fraction
with more than one term.

[2] If we have an Egyptian fraction we can make an equivalent
Egyptian fraction by expanding its smallest unit fraction into an
Egyptian fraction of more than one term.

3 (d) [5 marks] *How many different valued
fractions (a/b) are there if 0 < a < b < 1000? *

The calculation of this quantity can be done using a simple program. For each combination 0 < a < b < 1000, a/b should only be counted if there is no integer c > 1 that divides both b and a -- if there is, it will have the same value as (a/c)/(b/c) and will have been counted.

There are many ways of finding the greatest common divisor. A
very simple and fast algorithm is that of Euclid. This uses the
fact that

GCD(a, b) = GCD(b mod a, a)

where 0 < a < b. Repeating this formula will lead to the
first number being zero and the second the GCD. This is
implemented by the following Java code:

public int greatestCommonDivisor(int a, int b) { if (a == 0) return b; else return greatestCommonDivisor(b % a, a); }

The problem can be solved by a simple main procedure, also given in Java:

public void run() { int a, b; int count = 0; for( b = 2; b < 1000; b++ ) for( a = 1; a < b; a++ ) if (greatestCommonDivisor(b, a) == 1) count++; out.println(count); }

A solution using these procedures can be run in a Java-capable browser: example solution of part 3(d).

**Marking**

[5] 303791

(**Supplementary**: 304191 scores [4] marks.)

This is the case for 0 < a < b <= 1000.

- Example solution program for 3(a) and for 3(d).
- Question statement
- Index of BIO'97 Round One questions
- BIO'98 sample paper