Menu

Subscribe

Project Euler Problem 21

on project euler, erlang, python

Amicable numbers.

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.

Link to original description
Source code examples on Github

Erlang version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p20
% vim:syn=erlang

-mode(compile).

main(_) ->
    io:format("Answer: ~p ~n", [lists:sum(lists:flatten([fr(X) || X<-lists:seq(1,10000)]))]).

fr(X) ->
    D1 = d(X),
    case d(D1) of
        X when X < D1 -> [X, D1];
        _             -> []
    end.

d(0) -> 0;
d(N) -> lists:sum([X||X<-lists:seq(1,N div 2 + 1), N rem X =:= 0]).

Erlang version 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p20
% vim:syn=erlang

-mode(compile).

main(_) ->
    io:format("Answer: ~p ~n", [lists:sum(lists:flatten([fr(X) || X<-lists:seq(1,10000)]))]).

fr(X) ->
    D1 = lists:sum(d(X, 1,[])),
    case lists:sum(d(D1,1,[])) of
        X when X < D1 -> [X, D1];
        _             -> []
    end.

d(0, _, _)                    -> [];
d(N, M, A) when M > N div 2+1 -> A;
d(N, M, A) when N rem M =:= 0 -> d(N, M+1, [M|A]);
d(N, M, A)                    -> d(N, M+1, A).

Python version

1
2
3
4
5
6
7
8
9
#!/usr/bin/python

def divisors(n): 
    return list(i for i in xrange(1, n/2+1) if n % i == 0)

pair = dict( ((n, sum(divisors(n))) for n in xrange(1, 10000)) )

print sum(n for n in xrange(1, 10000) if pair.get(pair[n], 0) == n and pair[n] != n)