Saturday, January 24, 2009

Erlang solution for Euler problem 21

In project Euler problem number 21 we are asked to evaluate the sum of all amicable pairs under 10000.

To determine whether a given number N1 is an amicable number we determine the sum of all divisors of N1. This gives us another number N2. If N1 and N2 form an amicable pair, then the sum of the divisors of N2 should be N1 again. And also, we have to ignore all solutions where N1 = N2.

Once we have written the function is_amicable_pair/1 as described above, we simple try all number from 1 thru 9999 and sum all amicable numbers we find.

Here is the Erlang code:

%% Project Euler, problem 21
%%
%% Evaluate the sum of all amicable pairs under 10000.

-module(euler21).
-author('Cayle Spandon').

-export([solve/0, sum_of_divisors/1, is_amicable/1]).

sum_of_divisors(N) ->
sum_of_divisors(N, 1, N div 2, 0).

sum_of_divisors(N, Try, MaxTry, Sum) ->
if
Try > MaxTry ->
Sum;
N rem Try == 0 ->
sum_of_divisors(N, Try + 1, MaxTry, Sum + Try);
true ->
sum_of_divisors(N, Try + 1, MaxTry, Sum)
end.

is_amicable(N) ->
CandidateOther = sum_of_divisors(N),
ShouldBeN = sum_of_divisors(CandidateOther),
(N == ShouldBeN) and (N /= CandidateOther).

sum_of_amicable_numbers(N) ->
sum_of_amicable_numbers(1, N, 0).

sum_of_amicable_numbers(Try, MaxTry, Sum) ->
IsAmicable = is_amicable(Try),
if
Try >= MaxTry ->
Sum;
IsAmicable ->
sum_of_amicable_numbers(Try + 1, MaxTry, Sum + Try);
true ->
sum_of_amicable_numbers(Try + 1, MaxTry, Sum)
end.

solve() ->
solve(10000).

solve(N) ->
sum_of_amicable_numbers(N).

No comments: