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
I'm sure there are specially properties involving the conditions of amicable pairs. However, I did not exploit this and used factorazation again. What I should have done is used the multplicative property of sum of divisors formula to calculate each d(n)
My code contains three main functions:
There's a neat formula for calculating the sum of divisors: $$\Pi_{i=1}^k \frac{p_i^{m_i+1} - 1}{p_i -1 } $$
There's a neat intuitive way of understand this formula. To formulate a divisor, we can take any combination of primes and any combinations of their associated powers. For example, 24 can be represented by 23 x 3.
Factors are 1, 2, 3, 4, 6, 8, 12, 24
If we look at these factors, we see that each one of them are some combination of
Hence, we can determine the some this way:
$$ (1 + 2^0 + 2^1 + 2^2 + 2^3) * (1 + 3^0 + 3^1) $$
We see that if we "FOIL" (Front, outside, inside, last), if you remember from middle school, we get all the factors that are listed above. Looking at each product, we seee that they are basically geometric sum of the primes up to each power. Hence, we get that formula above for any generic number. It's pretty nice!
Answer: 648
Runtime: 0.53 ms