Puzzles

Prior to 2001 Puzzles

11 July 1999 (Be My Friend)

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:

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 ]

Puzzles

Prior to 2001 Puzzles

11 July 1999 (Be My Friend)

Brian’s Casio Calculator Corner