Finding amicable numbers with Linq

• Tweet
• Email

• Tweet
• Email

As a (somewhat lapsed but still interested) mathematician, I like to play around with interesting numbers. Well, I guess we all have our little foibles eh?

Anyway, I was contemplating the idea of amicable numbers last night. The short explanation of these is as follows…

An “amicable pair” of numbers consists of two numbers, p and q where p is the sum of q‘s divisors, and q is the sum of p‘s divisors. The smallest such pair is 220 and 284. The divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, which add up to 284, and the divisors of 284 are 1, 2, 4, 71 and 142, which add up to 220.

So, I decided to see if I could write some Linq to find pairs of amicable numbers. As usual, my interest here was in elegant code, not necessarily the most efficient algorithm.

Let’s start with perfection

A “perfect” number is one that is the sum of its divisors. For example, the number 6 can be divided by 1, 2 and 3 (ignoring 6 itself), and 1 + 2 + 3 = 6. There aren’t that many of these around, 6, 28, 496 and 8128 being the only ones less than 100,000, as we can see…

Finding perfect numbers was fairly easy. Note that when you look for divisors of a number n, you only need to go as far as n / 2, as there can’t be any divisors (other than n itself) greater than that. If it’s not clear why that is, try picking some numbers and writing down their divisors. So, to find the divisors of a number n, all we need to do is generate a sequence of numbers 1 to n / 2, and see which numbers evenly divide into n. Et voila…

Enumerable.Range(1, n / 2).Where(n1 => n % n1 == 0)

Finding all perfect numbers less that (say) 1000 is now as easy as…

Enumerable.Range(1, 1000)
  .Where(n => Enumerable.Range(1, n / 2).Where(n1 => n % n1 == 0).Sum() == n)

This gives the first three perfect numbers.

Getting amicable

Note that we switch to using p and q instead of n to make it clearer which number in the pair we mean.

To find amicable pairs, we can do the following for every number p in our target range…

1. Calculate the sum of p‘s divisors. This gives us a second number q which is to be checked to see if it forms an amicable pair with p
2. Calculate the sum of q‘s divisors and see it is is equal to p. If so, we have an amicable pair

So, a first bash at this could look like…

Enumerable.Range(1, 1000)
  .Select(p => new { P = p, Q = Enumerable.Range(1, p / 2).Where(p1 => p % p1 == 0).Sum() })  
  .Where(data => data.P == Enumerable.Range(1, data.Q / 2).Where(q1 => data.Q % q1 == 0).Sum())

The Select clause returns an anonymous type (and yes, I could just as easily have used a tuple) that contains the original number p, and the sum of its divisors, ie our candidate q.

The Where clause then filters this list for the cases where the sum of q‘s divisors equals p.

This is fine, but ignores two issues. First, every perfect number forms an amicable (if somewhat anti-social) pair with itself. This is obvious, as the sum of p‘s divisors obviously adds up to p for a perfect number. Secondly, every amicable pair appears twice, once with the smaller number first and once with the larger number first. In other words, the above code returns the following…

As you can see, this list includes 6, 28 and 496, the first three perfect numbers, but also includes the amicable pair (220, 284) twice, once like that and once as (284, 220).

Therefore, our algorithm above has to be modified to exclude these cases. I originally wasted spent some time handling the two cases separately, until it dawned on me that both cases could be considered by only including pairs where the first number was less than the second. This left me with the following…

Enumerable.Range(1, 5000)
  .Select(p => new { P = p, Q = Enumerable.Range(1, p / 2)
                                  .Where(p1 => p % p1 == 0).Sum() })
  .Where(data => data.P < data.Q
              && data.P == Enumerable.Range(1, data.Q / 2)
                             .Where(q1 => data.Q % q1 == 0).Sum())

Using 5000 as the upper bound, this took about a second to find the first three amicable pairs.