Problem 21 : Amicable Numbers

Amicable numbers

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are 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.

                                                                                                       (https://projecteuler.net/problem=21)

Kudos to the one who found out amicable numbers!

Studying amicable numbers allows you to explore the deeper side of the nature of numbers, and you will be amazed at their intrinsic properties involving factors.

If we denote that for an amicable pair (m, n):


where

                 

where   is the divisor function.

And therefore we can derive the fact that:

                

(Learn more about amicable numbers.)

As the problem stated, the most well-known amicable pair is (220, 284), as they are the first amicable numbers and the only numbers under 1000.



Let's get into the problem-solving.

The most important function will be finding the sum of the proper divisors.

public static int sumFactor(int n) {...}

As always, we need the base case.

if (n == 0) return 0;

Let's initialize the sum as 1, for the sum of the proper divisors will always be at least 1 (prime numbers will have the sum of the proper divisors of 1):

int sum = 1;

As discussed in the problem 3, our limit for the division will be the square root of the number:

int sqrt = (int) Math.sqrt(n);

Starting with 2, we will check the divisibility and add BOTH the divisor and paired divisors (for example, if 36 is divisible by 3, then we add 3 and its paired divisor 12, or 36 divided by 3):

for (int i = 2; i <= sqrt; i++)
{
    if (n%i == 0) sum += i + n/i;
}

Last step is to check if the number is a perfect square. So if the number is 25, then in the previous step we added 5 twice as the divisor is 5 and its paired divisor is also 5. We need to get rid of this redundancy):

if (n == sqrt*sqrt) sum -= sqrt;

Combined algorithm:

public static int sumFactor(int n)
{
    if (n == 0) return 0;
    int sum = 1;
    int sqrt = (int) Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++)
    {
        if (n%i == 0) sum += i + n/i;
    }
    if (n == sqrt*sqrt) sum -= sqrt;
    return sum;
}

Now, we want to know if the number is amicable number.

The one thing I want to point out is that an amicable pair cannot contain a duplicate number.

For example, 6 has proper divisors of 1,2, and 3, so s(6) = 1 + 2 + 3  = 6.

6 is an "amicable number" of itself, which is against the definition of amicable number.

So we need the condition that a != s(a)

public static boolean isAmicable(int a)
{
    int b = sumFactor(a);
    return (a != b) && (a == sumFactor(b));
}

We are all set! Let's iterate through the integers until we reach 10,000:

int sum = 0;
for (int i = 1; i < 10000; i++)
    if (isAmicable(i)) sum += i;
System.out.println(sum);

Answer is 31626
Execution time is 8.740898 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem021.java