The British Informatics Olympiad Sponsored 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

Question statement

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.

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.

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

• 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