The problem statement from the Ole Miss Problems of the Week page is:

Two integers are said to be *amicable* or *friendly*
if each number is the sum of all the possible divisors of the other.
One such pair is 220 and 284.
Since the possible divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22,
44, 55, and 110 which sum to 284 and the possible divisors of 284
are 1, 2, 4, 71, and 142 which sum to 220, then 220 and 284 are
said to be friendly.
Find a pair of friendly numbers such that both integers are greater
than 1100 and less than 1300.
Hint: this pair was found in 1866 by a 16 year-old named
Nicolo Paganini.

Well, obviously the first thing to do is to follow up on the hint. However, various web searches for Nicolo Paganini turn up a great deal of information on the composer who died in 1840, rather than a mathematician who was born in 1850. Sigh. It looks like we will have to solve this problem.

Once again, we have a search that we can program on the CFX-9850G or FX-7400G programmable graphics calculator. The search range — 1100 to 1300 — is small enough that we can simply enumerate it without further ado. Unfortunately, the size of the search space is effectively multiplied by the size of the divisor search. For each of the numbers in the search space, we need to search for divisors.

To find the divisors of *n*, we could check each of the
numbers 1, 2, ..., *n*-1.
Unfortunately, this requires about *n* operations.
We need something faster.
We could factor *n*, then combine the factors into divisors —
but that would require all the work of factoring, then 2^{f}
operations, where *f* is the number of factors, for combining
the factors, and the bookkeeping for combining the right factors would
be a pain.
But the thought of factors reminds us that when factoring a number *n*,
we need only to test up to √*n* — the quotient after
a division with no remainder is also a factor.
We can write the divisor test the same way: test each number from 2 (inclusive)
to √*n* (exclusive), and if it divides *n* then both
the divisor and the quotient are divisors.
The square root of *n* has to be handled specially, as we want to
count it only once as a divisor.
And 1 has to be handled specially, as we want to count 1 but not *n*
itself as a factor.

Now, we can write a little subroutine to add up the divisors of a number. We present this here and in a text file with .CAT file contents. As usual, semicolon (“;”) starts a comment that is not to be entered into the calculator.

Program P071199A (90 bytes):

; Variables: ; A is the number for which the sum of the factors is to be found ; B is the sum of factors ; C is the candidate factor ; D is the quotient of A and the candidate factor ; Symbols: ; -> is assignment arrow ; x^2 is square operator ; / is division operator ; = is equality relational 0->B ; Zero sum of divisors 2->C ; 2 is initial divisor While Cx^2<A ; Loop through possible lower divisors A/C->D ; Get quotient If Frac D=0 ; Test whether division had no remainder Then B+C+D->B ; If so, accumulate divisor and quotient both IfEnd ; [End of test whether division had no remainder] C+1->C ; Increment candidate divisor WhileEnd ; [End of loop through possible lower divisors] If Cx^2=A ; Test whether the number is a square Then B+C->B ; If so, square root is also a divisor IfEnd ; [End of test whether number is a square] B+1->B ; And 1 is a divisor

Now we need to program main search loop. For each candidate between 1100 and 1300, we compute the sum of the divisors. If the sum of divisors is between 1100 and 1300, we compute the sum of divisors of the sum of divisors. If that is the original number, we have a friendly pair. Also, we require that the sum of the divisors of the original number be at least as large as the original number: if it is less than the original number, we have already looked at it.

Program P071199 (131 bytes):

; Variables: ; A is argument to P071199A ; B is result from P071199A ; C is used by P071199A ; D is used by P071199A ; E is candidate (1100 to 1300) ; F is sum of divisors of candidate ; Symbols: ; -> is assignment arrow ; <= is less than or equal to relational ; >= is greater than or equal to relational ; _ is display triangle 1100->E ; Get lowest candidate While E<=1300 ; Loop through all candidates E->A ; Get sum of divisors of Prog "P071199A" ; candidate into B If 1100<=B And B<=1300 And B>=E ; Test if sum of divisors are in range Then B->F ; If so, save sum of divisors F->A ; Get sum of divisors of Prog "P071199A" ; sum of divisors into B If B=E ; Test whether that is the original number Then 10000E+F_ ; If so, report the pair as two four-digit ; numbers on one line IfEnd ; [End of test whether is original number] IfEnd ; [End of test if sum of divisors in range] E+1->E ; Advance to next candidate WhileEnd ; [End of loop through all candidates] "Done" ; Report completion

Now we run this program, and after about a minute and half, it produces the line:

11841210

which we interpret as the pair of numbers 1184 and 1210. After a few minutes more, the program produces:

Done

which indicates this is the only pair of friendly numbers in the range 1100 to 1300.

Out of curiosity, we can remove the range test on the friends of the numbers we find, and start the search at 1 instead of 1100. This yields the outputs:

10001 60006 280028 2200284 4960496 11841210

This verifies that our tests find the friendly numbers 220 and
284.
This also finds numbers 1, 6, 28, and 496 that are friendly with
themselves.
These numbers are called *perfect* numbers — the
sums of their divisors are the numbers themselves.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.