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.

About these ads

Pages: 1 2

2 Responses to “Amicable Chains”

  1. matthew said

    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");
          }
        }
      }
    }
    
  2. Mike said

    Basically, came up with a Python version of Mathew’s solution.

    def findchains(limit=1000000):
    	divsum = [0]*limit
    	for n in range(1, limit//2):
    		for i in range(2*n, limit, n):
    			divsum[i] += n
    
    	chains = []
    	for n in range(2, limit):
    		chain = []
    		while 1 < divsum[n] < limit:
    			chain.append(n)
    			divsum[n], n = -divsum[n], divsum[n]
    
    		if -divsum[n] in chain:
    			chain = chain[chain.index(n):]
    			start = chain.index(min(chain))
    			chain = chain[start:] + chain[:start]
    			chains.append(chain)
    
    	return sorted(chains, key=lambda x:(len(x),x))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: