Amicable Chains
May 20, 2014
A perfect number is equal to the sum of its proper divisors; for instance, the divisors of 28 are 1, 2, 4, 7, and 14, and 1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number. Two numbers m and n form an amicable pair if the sum of the divisors of m equals n and the sum of the divisors of n equals m; for instance, 220 has divisors 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 which sum to 284, and 284 has divisors 1, 2, 4, 71, 142 which sum to 220, so 220 and 284 form an amicable pair. An amicable chain is a list of numbers, each the sum of the divisors of the previous number, that loops so that the sum of the divisors of the last number in the list is the first number in the list; for instance, the numbers 12496, 14288, 15472, 14536, and 14264 form an amicable chain of length 5, since sum-div(12496) = 14288, sum-div(14288) = 15472, sum-div(15472) = 14536, sum-div(14536) = 14264, and sum-div(14264) = 12496. We discussed amicable numbers in a previous exercise.
Your task is to write programs to locate perfect numbers, amicable numbers and amicable chains; use it to find all of those objects for which all of their elements are less than a million. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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.