Amicable Numbers (PE21)

The 21st problem on Project Euler states,

"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'll first define a function, \(d(n)\).

d(n) = [ k for k in 1:n-1 if n % k == 0 ] |> sum

Next, we'll need some driver code to check all of the numbers under \(10,000\).

N = 10_000
checked = falses(3N)
pairs = Pair{Int, Int}[]
for a in 2:N
    if checked[a] == false
        checked[a] = true
        b = d(a)
        checked[b] = true
        if d(b) == a && a ≠ b
            push!(pairs, Pair(a, b))
        end
    end
end

reduce((acc, iter) -> acc + iter[1] + iter[2], pairs, init=0)

>   0.209513 seconds (146.66 k allocations: 8.028 MiB, 3.76% gc time, 6.53% compilation time)
> 
>  31626

In this code snippet, we create an array of booleans using falses so we can avoid double checking numbers we've already checked. If the checked array shows a number hasn't yet been checked, then we check to see if \(d(a) = d(b)\) where \(a \neq b\). If both criteria pass, then we add the pair into our array of pairs.

Finally, we use the reduce function to sum them up yielding the final result.