Amicable Chains
May 20, 2014
A simple way to compute the divisors of a number n is try each integer from 1 to ⌊n/2⌋ and see if it divides n:
(define (divisors n)
(let loop ((i 1) (ds (list)))
(cond ((< n (+ i i)) (reverse ds))
((zero? (modulo n i))
(loop (+ i 1) (cons i ds)))
(else (loop (+ i 1) ds)))))
> (divisors 220)
(1 2 4 5 10 11 20 22 44 55 110)
> (divisors 284)
(1 2 4 71 142)
> (divisors 36)
(1 2 3 4 6 9 12 18)
Note that we are excluding n from the list of divisors of n; that’s what we want when computing amicable pairs, but in some cases you might want to add n to the list of divisors of n. Instead of making a list of divisors, we can compute their sum:
(define (sum-div n)
(let loop ((i 1) (s 0))
(cond ((< n (+ i i)) s)
((zero? (modulo n i))
(loop (+ i 1) (+ s i)))
(else (loop (+ i 1) s)))))
> (sum-div 220)
284
> (sum-div 284)
220
> (sum-div 36)
55
Instead of counting up to ⌊n/2⌋, it is faster to note that divisors appear in pairs, so it is only necessary to count up to the square root of n; be careful when n is a perfect square to include exactly one instance of the square root in the sum:
(define (divisors n)
(let loop ((i 2) (ds (list 1)))
(cond ((<= n (* i i))
(sort < (if (= n (* i i)) (cons i ds) ds)))
((zero? (modulo n i))
(loop (+ i 1) (cons i (cons (/ n i) ds))))
(else (loop (+ i 1) ds)))))
(define (sum-div n)
(let loop ((i 2) (s 1))
(cond ((<= n (* i i))
(if (= n (* i i)) (+ i s) s))
((zero? (modulo n i))
(loop (+ i 1) (+ s i (/ n i))))
(else (loop (+ i 1) s)))))
> (divisors 220)
(1 2 4 5 10 11 20 22 44 55 110)
> (divisors 284)
(1 2 4 71 142)
> (divisors 36)
(1 2 3 4 6 9 12 18)
> (sum-div 220)
284
> (sum-div 284)
220
> (sum-div 36)
55
If you know the prime factorization of n, it is easy to find the divisors of n: simply take the products of the members of the powerset of the factor of n, eliminating duplicates.
(define (but-last xs)
(if (null? xs) (error 'but-last "empty list")
(reverse (cdr (reverse xs)))))
(define (unique eql? xs)
(cond ((null? xs) '())
((null? (cdr xs)) xs)
((eql? (car xs) (cadr xs)) (unique eql? (cdr xs)))
(else (cons (car xs) (unique eql? (cdr xs))))))
(define (power-set xs)
(if (null? xs) (list (list))
(let ((rest (power-set (cdr xs))))
(append (map (lambda (x) (cons (car xs) x)) rest) rest))))
(define (divisors n)
(but-last (unique = (sort <
(map (lambda (xs) (apply * xs))
(power-set (factors n)))))))
> (divisors 220)
(1 2 4 5 10 11 20 22 44 55 110)
> (divisors 284)
(1 2 4 71 142)
> (divisors 36)
(1 2 3 4 6 9 12 18)
It is even easier to find the sum of the divisors of n if you know the prime factorization of n by examining the multiplicities of the factors of n:
(define (sum-div n)
(define (div f x) (/ (- (expt f (+ x 1)) 1) (- f 1)))
(let ((fs (factors n)))
(let loop ((f (car fs)) (fs (cdr fs)) (x 1) (s 1))
(cond ((null? fs) (- (* s (div f x)) n))
((= (car fs) f) (loop f (cdr fs) (+ x 1) s))
(else (loop (car fs) (cdr fs) 1 (* s (div f x))))))))
> (sum-div 220)
284
> (sum-div 284)
220
> (sum-div 36)
55
A simple method to find the factors of a number n uses a prime wheel; this is slow if n is a large prime or semi-prime but reasonable otherwise:
(define (factors n)
(define (last-pair xs) (if (null? (cdr xs)) xs (last-pair (cdr xs))))
(define (cycle . xs) (set-cdr! (last-pair xs) xs) xs)
(let ((wheel (cons 1 (cons 2 (cons 2 (cycle 4 2 4 2 4 6 2 6))))))
(let loop ((n (abs n)) (f 2) (wheel wheel) (fs (list)))
(cond ((< n (* f f)) (if (= n 1) fs (reverse (cons n fs))))
((zero? (modulo n f)) (loop (/ n f) f wheel (cons f fs)))
(else (loop n (+ f (car wheel)) (cdr wheel) fs))))))
Given all this, it is easy to determine if a number n is perfect, or if it is part of an amicable pair:
(define (perfect? n)
(= n (sum-div n)))
(define (amicable? n)
(let ((s (sum-div n)))
(and (< 1 s) (= (sum-div s) n))))
> (perfect? 6)
#t
> (perfect? 28)
#t
> (amicable? 220)
#t
> (amicable? 284)
#t
It is also easy to find the perfect numbers and amicable pairs less than some limit:
(define (perfect limit)
(let loop ((n 2) (ps (list)))
(cond ((< limit n) (reverse ps))
((= n (sum-div n))
(loop (+ n 1) (cons n ps)))
(else (loop (+ n 1) ps)))))
(define (amicable limit)
(let loop ((n 2) (as (list)))
(if (< limit n) (reverse as)
(let ((s (sum-div n)))
(if (and (< n s) (= n (sum-div s)))
(loop (+ n 1) (cons (list n s) as))
(loop (+ n 1) as))))))
> (perfect 10000)
(6 28 496 8128)
> (amicable 10000)
((220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368))
Instead of factoring each number up to a limit, it is much faster to find the sums of the divisors of all numbers up to a limit by sieving: Make a vector from 1 to the limit, each item initialized to 1. Then, for each i from 2 to the limit, add i to each multiple of i:
(define (make-sum-divs n)
(let ((s (make-vector (+ n 1) 0)))
(do ((i 1 (+ i 1))) ((< n i) s)
(do ((j (+ i i) (+ j i))) ((< n j))
(vector-set! s j (+ i (vector-ref s j)))))))
(define max-sum-div 1000)
(define sum-divs (make-sum-divs max-sum-div))
Given the sieve, it is easy to find perfect numbers and amicable pairs:
(define (perfect limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((n 2) (ps (list)))
(cond ((< limit n) (reverse ps))
((= n (vector-ref sum-divs n))
(loop (+ n 1) (cons n ps)))
(else (loop (+ n 1) ps)))))
(define (pairs limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((n 2) (as (list)))
(if (< limit n) (reverse as)
(let ((s (vector-ref sum-divs n)))
(if (and (< s max-sum-div) (< n s)
(= n (vector-ref sum-divs s)))
(loop (+ n 1) (cons (list n s) as))
(loop (+ n 1) as))))))
> (perfect 1000000)
(6 28 496 8128)
> (pairs 1000000)
((220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368)
(10744 10856) (12285 14595) (17296 18416) (63020 76084)
(66928 66992) (67095 71145) (69615 87633) (79750 88730)
(100485 124155) (122265 139815) (122368 123152)
(141664 153176) (142310 168730) (171856 176336)
(176272 180848) (185368 203432) (196724 202444)
(280540 365084) (308620 389924) (319550 430402)
(356408 399592) (437456 455344) (469028 486178)
(503056 514736) (522405 525915) (600392 669688)
(609928 686072) (624184 691256) (635624 712216)
(643336 652664) (667964 783556) (726104 796696)
(802725 863835) (879712 901424) (898216 980984))
The sieving method is much faster than either of the other two methods. On my computer, it takes twelve seconds to compute the amicable pairs less than a million using trial division to find the divisors, and about the same amount of time for the factoring method, but only about a second-and-a-half to sieve the divisor sums to a million and another half-a-second to find the amicable pairs, a total of two seconds.
The program to find amicable chains is a variant of the program to find amicable pairs:
(define (chain n limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((s (vector-ref sum-divs n)) (cs (list n)))
(cond ((= s n) (reverse cs))
((not (< n s limit)) (list))
((member s cs) (list))
(else (loop (vector-ref sum-divs s) (cons s cs))))))
(define (chains limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((n 2) (cs (list)))
(if (< limit n) (reverse cs)
(let ((c (chain n limit)))
(if (null? c) (loop (+ n 1) cs)
(loop (+ n 1) (cons c cs)))))))
> (sort (lambda (a b) (< (length a) (length b))) (chains 1000000))
((6) (28) (496) (8128) (220 284) (1184 1210) (2620 2924)
(5020 5564) (6232 6368) (10744 10856) (12285 14595)
(17296 18416) (63020 76084) (66928 66992) (67095 71145)
(69615 87633) (79750 88730) (100485 124155) (122265 139815)
(122368 123152) (141664 153176) (142310 168730)
(171856 176336) (176272 180848) (185368 203432)
(196724 202444) (280540 365084) (308620 389924)
(319550 430402) (356408 399592) (437456 455344)
(469028 486178) (503056 514736) (522405 525915)
(600392 669688) (609928 686072) (624184 691256)
(635624 712216) (643336 652664) (667964 783556)
(726104 796696) (802725 863835) (879712 901424)
(898216 980984) (12496 14288 15472 14536 14264)
(14316 19116 31704 47616 83328 177792 295488 629072 589786
294896 358336 418904 366556 274924 275444 243760 376736
381028 285778 152990 122410 97946 48976 45946 22976 22744
19916 17716))
The four perfect numbers form amicable chains of length 1, there are 40 amicable pairs, there is an amicable chain of length 5 mentioned above, and notice the spectacular amicable chain of length 28 that starts at 14316.
You can run the program at http://programmingpraxis.codepad.org/fujimea2.
Programming Praxis 
NIce problem. Here is a C++ solution. Use a sieve to build up divisor sums, then go through array marking chains with a unique label; when we come to an already marked entry, if the label is the same as the current one, we have found a loop (of length >= 1), so print it out. Runtime 0.1s for N = 1000000, mostly building up divisor sums.
#include <stdio.h> #include <stdlib.h> #include <vector> using namespace std; int main(int argc, char *argv[]) { int N = atoi(argv[1]); vector<int> a(N+1); // a[i] = divisor sums of i vector<int> b(N+1); // b[i] = b[j] if j is on a chain from i for (int i = 1; i <= N/2; i++) { for (int j = 2*i; j <= N; j += i) { a[j] += i; // Divisor sum } } b[0] = -1; // Mark 0 as visited. for (int i = 1; i <= N; i++) { if (b[i] == 0) { // We haven't been here before int j = i; do { b[j] = i; // Scan forward j = a[j]; } while (j <= N && b[j] == 0); if (j <= N && b[j] == i) { // We are back to the current chain, so print the loop int k = j; do { printf("%d ", k); k = a[k]; } while (k != j); printf("\n"); } } } }Basically, came up with a Python version of Mathew’s solution.