Erlang library for Project Euler

max_heap.erl

-module(max_heap).
-export([new/0, push/2, pop/1]).

new() -> empty.

push(X,H) -> merge({X,[]}, H).

pop({X,L}) -> {X, lists:foldl(fun merge/2, empty, pair(L))}.

merge(X,empty)     -> X;
merge(empty,X)     -> X;
merge({A,X},{B,Y}) when A >= B -> {A, [{B,Y}|X]};
merge({A,X},{B,Y}) -> {B, [{A,X}|Y]}.

pair([A,B|T]) -> [merge(A,B)|pair(T)];
pair(X)       -> X.

min_heap.erl

-module(min_heap).
-export([new/0, push/2, pop/1]).

new() -> empty.

push(X,H) -> merge({X,[]}, H).

pop({X,L}) -> {X, lists:foldl(fun merge/2, empty, pair(L))}.

merge(X,empty)     -> X;
merge(empty,X)     -> X;
merge({A,X},{B,Y}) when A =< B -> {A, [{B,Y}|X]};
merge({A,X},{B,Y}) -> {B, [{A,X}|Y]}.

pair([A,B|T]) -> [merge(A,B)|pair(T)];
pair(X)       -> X.

ppt.erl

%%%%  Primitive Pythagorean triples.

-module(ppt).
-export([triples/0]).

triples() -> triples({3,4,5}).

triples({A,B,C}) ->
    L = [next_triples(T) || T <- [{-A,B,C},{-A,-B,C},{A,-B,C}]],
    {{A,B,C}, [fun () -> triples(X) end || X <- L]}.

next_triples({A,B,C}) -> {-A-2*B+2*C, -2*A-B+2*C, -2*A-2*B+3*C}.

prime_factors.erl

-module(prime_factors).
-export([facts/1, count_factors/1, sum_factors/1]).

facts(N) when N < 2 -> [];
facts(N)            -> facts(N, 2, []).

facts(N,P,[{N,V}|T]) when N < P*P       -> [{N,V+1}|T];
facts(N,P,L)         when N < P*P       -> [{N,1}|L];
facts(N,P,[{P,V}|T]) when N rem P =:= 0 -> facts(N div P, P, [{P,V+1}|T]);
facts(N,P,L)         when N rem P =:= 0 -> facts(N div P, P, [{P,1}|L]);
facts(N,2,L)                            -> facts(N, 3, L);
facts(N,P,L)                            -> facts(N, P+2, L).

count_factors(N) ->
    lists:foldl(fun ({_,V}, Acc) -> (V+1)*Acc end, 1, facts(N)).

sum_factors(N) when N < 2 -> 0;
sum_factors(N) ->
    F = fun ({P,E}) ->
            G = fun (X) -> trunc(math:pow(P,X)) end,
            lists:sum(lists:map(G, lists:seq(0,E)))
        end,
    prod(lists:map(F, facts(N))) - N.

prod(L) -> lists:foldl(fun (X,Y) -> X*Y end, 1, L).

primes.erl

-module(primes).
-export([list/1, array/1, is_prime/1]).

-define(K, fun(X,_) -> X end).
-define(even(N), N rem 2 =:= 0).

%%%% primes list & array

list(Max) ->
    set_primes(Max),
    ?K(lists:sort(get_keys(true)), erase()).

array(Max) ->
    set_primes(Max-1),
    A = array:from_orddict(lists:sort(get()), false),
    ?K(array:resize(Max,A), erase()).

set_primes(Limit) ->
    F = fun (N) -> put(2*N+1, true) end,
    lists:foreach(F, lists:seq(1, (Limit-1) div 2)),
    put(2, true),
    sieve(3, 3, Limit).

sieve(M,_,Limit) when M*M > Limit -> ok;
sieve(M,N,Limit) when M*N > Limit -> sieve(M+2, M+2, Limit);
sieve(M,N,Limit) -> erase(M*N), sieve(M, N+2, Limit).

%%%% is_prime

is_prime(N) when N < 2 -> false;
is_prime(2) -> true;
is_prime(N) when ?even(N) -> false;
is_prime(N) when N < 4759123141 ->
    miller_rabin([2,7,61], N, min_odd(N-1));
is_prime(N) when N < 341550071728321 ->
    miller_rabin([2,3,5,7,11,13,17], N, min_odd(N-1)).

miller_rabin([H|R],N,T) when H < N ->
    Y = powm(H,T,N),
    case miller_rabin_sub(N,T,Y) of
        true  -> miller_rabin(R,N,T);
        false -> false
    end;
miller_rabin(_,_,_) -> true.

miller_rabin_sub(N,T,Y) when T =/= N-1, Y =/= 1, Y =/= N-1 ->
    miller_rabin_sub(N, 2*T, (Y*Y) rem N);
miller_rabin_sub(N,T,Y) when Y =/= N-1, ?even(T) -> false;
miller_rabin_sub(_,_,_) -> true.

min_odd(N) when ?even(N) -> min_odd(N div 2);
min_odd(N) -> N.

powm(_,0,_) -> 1;
powm(Base,P,M) when ?even(P) ->
    X = powm(Base, P div 2, M), X * X rem M;
powm(Base,P,M) ->
    Base * powm(Base, P-1, M) rem M.