Programming Praxis

We studied amicable chains in the previous exercise. Today we look at aliquot sequences, which are closely related to amicable chains. The aliquot sequence of n is the sequence that starts with n as its zero’th element and s(k−1) as its k‘th element, where s is the sum-of-divisors function of the previous exercise. For instance, the aliquot sequence of 10 is 10, 8, 7, 1, 0 because s(10) = 1 + 2 + 5 = 8, s(8) = 1 + 2 + 4 = 7, s(7) = 1, and s(1) = 0.

In 1888 Eugène Charles Catalan conjectured that all aliquot sequences end either at a prime number (the aliquot sequence for 10 shown above is usually considered to end at the prime 7, since once a member of an aliquot sequence is prime, the next two steps are 1 and 0) or at an amicable chain (either a perfect number which is an amicable chain of length 1, or an amicable pair which is an amicable chain of length 2, or a longer amicable chain). For instance, the aliquot sequence for 95 is 95, 25, 6, 6, …, where 6 is a perfect number. All numbers for which the entire aliquot sequence has been determined fit the conjecture, but there are many numbers for which the entire aliquot sequence is not known, of which the smallest is 276.

Your task is to write a function that computes aliquot sequences; it should return either the prime number or the amicable chain (smallest number first) that terminates the sequence. 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.

Pages: 1 2 3