# Amicable pairs

Published on 2011-07-27The next problem up in Project Euler concerns a rather exotic-sounding kind of number pairing: the amicable

pair. The problem itself contains a thorough definition and explanation of what defines such a pair:

Let d(

n) be defined as the sum of proper divisors ofn(numbers less thannwhich divide evenly inton).

If d(

a) =band d(b) =a, wherea≠b, thenaandbare an amicable pair and each ofaandbare called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

To find all amicable numbers under 10,000, I used the algorithm from my solution to problem 12 to find the divisors for all numbers between 1 and 9,999, and then searched an array constructed therefrom for amicable pairs.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem021 { class Program { static void Main(string[] args) { int[] pairs = new int[10000]; int divisors = 1; int sumOfAmicableNumbers = 0; for (int i = 1; i < 10000; i++) { for (int j = 2; j <= (int)Math.Sqrt(i); j++) { if (j == Math.Sqrt(i)) break; if (i % j == 0) divisors += j + (i / j); } pairs[i] = divisors; divisors = 1; } for (int i = 1; i < 10000; i++) { if (pairs[i] < 10000) { if (i != pairs[i] && i == pairs[pairs[i]]) { sumOfAmicableNumbers += i; } } } Console.WriteLine(sumOfAmicableNumbers); } } }