The British
Informatics OlympiadSponsored by Data Connection. |

Sample Paper: Solution to
Question 1 |

- Question statement
- Solution to part (a) (b)
- Description of solution program - (amicable.pas)
- Return to the BIO'97 sample paper index

Two numbers are said to be 'amicable' if they are different and the sum of the divisors of each number (including 1 but excluding the number itself) equals the other number.

For example: 2620 is divisible by 1, 2, 4, 5, 10, 20, 131, 262, 524, 655 and 1310; these add up to 2924. 2924 is divisible by 1, 2, 4, 17, 34, 43, 68, 86, 172, 731 and 1462; these add up to 2620. Therefore 2620 and 2924 are amicable.

This question requires the ability to test whether one number
exactly divides another. There are many ways to do this, but C
and Pascal provide remainder functions. In C, `((A % B) == 0)`
is true if B divides A. The Pascal equivalent is `((A mod B) =
0)`.

Amicable numbers are closely related to perfect numbers: the sum of the divisors of a perfect number equals the number. It is also possible to have numbers that are three-way amicable, such as:

- Sum-of-divisors(A) = B

Sum-of-divisors(B) = C

Sum-of-divisors(C) = A

and so on.

Sample
run |
|||

1 (a) [20 marks] |
Write a program which inputs two numbers (which will be less than 10,000) and then prints "Amicable" if they are amicable, or "Not amicable" otherwise. Your program should then terminate. | First
number: 2620Second number: 2924Amicable |

We begin this solution by writing a function which returns
the sum of the divisors of a specified number. The Pascal
function `Likes` takes a 16-bit unsigned integer `n`
as its parameter, then cycles through the numbers `1` to `n-1`,
adding those that exactly divide `n`. It returns the sum.
The code is as follows:

function Likes(n: Word): Word; { returns the sum of the divisors of n } var i, x: Word; begin x := 0; for i := 1 to (n - 1) do if (n mod i) = 0 then x := x + i; Likes := x; end;

Once the program has read in two numbers `a` and `b`,
the code to test if they are amicable is also simple:

if (Likes(a) = b) and (Likes(b) = a) and (a <> b) then WriteLn(a:1, ' and ', b:1,' are amicable.') else WriteLn(a:1, ' and ', b:1,' are not amicable.');

**Marking**

20 marks are available for this part. Correctly characterising a number of pairs gets 12, broken down as:

Marks A, B Answer [2] 2620, 2924 Amicable [4] 6368, 6232 Amicable [2] 932, 1023 Not amicable [2] 1996, 1504 Not amicable [2] 496, 496 Not amicable

A further 8 marks can be obtained by: [2] program terminates
without crashing; [3] correctly inputting two numbers; [3]
printing `Amicable` or `Not amicable` for each
pair.

1 (b) [3 marks] |
Which is the lowest pair of amicable numbers? |

The solution to this part uses the function `Likes`. A
variable `i` counts from 2 upwards, testing each number to
see if it is part of an amicable pair. Once a pair is found, it
stops and displays the result:

var i, j: Word; i := 2; while i < 30000 do begin j :="Likes(i);" if (likes(j)="i)" and (j <> i) then begin WriteLn('The first pair of amicable numbers is ', i:1, ' and ', j:1); i := 30000; end; Inc(i); end;

**Marking**

3 marks are obtained if the correct pair (220, 284) is given. If the solution to 1(a) incorrectly takes perfect numbers as amicable (e.g. by finding (496, 496) amicable), and gave the answer as (6, 6), 2 marks are awarded.

A total of 23 marks are available for question 1.

- Solution program amicable.pas
- Zipped source and executable amicable.zip (5,594 bytes)

The solution to this question can be found in Solution program
amicable.pas. The program is easy to
use, and the help text which can be obtained by typing `amicable
help` follows:

AMICABLE - finds amicable and perfect numbers. Copyright (C) 1997 The British Informatics Olympiad Usage: AMICABLE HELP shows this text AMICABLE enters interactive mode AMICABLE MIN displays first pair of amicable numbers. AMICABLE LIST lists amicable pairs up to 30000 AMICABLE n tests if n is perfect or amicable