Making BGP use some other port than 179.

By default BGP uses port 179 for both incoming and outgoing connections. This can be a problem because port 179 is a privileged port which can only be opened for listening as root.

Quagga can easily be configured to use some other port than 179.

Do the following to make BGP listen on port 1790 instead of port 179.

Edit the file /etc/quagga/debian.conf as root:

sudo vi /etc/quagga/debian.conf

Set the bgpd_options to the following:

bgpd_options="  --daemon -A 127.0.0.1 --bgp_port 1790"

Restart quagga as follows:

sudo /etc/init.d/quagga restart

Verify that BGP is actually listening on port 1790:

$ netstat -ant
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
tcp        0      0 0.0.0.0:1790            0.0.0.0:*               LISTEN
tcp6       0      0 :::1790                 :::*                    LISTEN

Do the following to make BGP use port 1790 instead of port 179 for outgoing connections:

Go into the CLI for BGP:

telnet localhost 2605
[...]
Password: zebra

Go into configuration mode:

bgpd> ena
bgpd# configure terminal

Configure BGP as follows:

router bgp xxxx
 neighbor x.x.x.x remote-as xxxx
 neighbor x.x.x.x port 1790

Save the configuration using the "write" command:

write

Verify that BGP actually uses 1790 as the outgoing port as follows (you can do a "clear ip bgp *" to make BGP initiate an outgoing connection faster):

$ sudo tcpdump port 1790
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 96 bytes
00:05:17.791499 IP cayle-spandons-ubuntu.local.51002 > cayle-spandons-computer.local.1790: S 395668408:395668408(0) win 5840 
00:05:17.792250 IP cayle-spandons-computer.local.1790 > cayle-spandons-ubuntu.local.51002: R 0:0(0) ack 395668409 win 0

Erlang.org course exercises for masters, slaves, and error handling.

The Erlang.org website contains one programming exercise dealing masters, slaves, and error handling.

The requirements are as follows (copied from the Erlang.org website):

Write a module ms with the following interface:

start(N) - Start the master and tell it to start N slave processes. Register the master as the registered process master.

to_slave(Message, N) - Send a message to the master and tell it to relay the message to slave N. The slave should exit (and be restarted by the master) if the message is die.

The master should detect the fact that a slave processes dies and restart it and print a message that it has done so.

The slave should print all messages it recieves except the message die

The source code for my solution is:

%% Erlang exercises: Masters and Slaves, error handling
%%
%% See http://erlang.org/course/exercises.html for details.

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

-export([start/1, stop/0, to_slave/2]).

start(NrSlaves) ->
    MasterPid = spawn(fun() -> master_start(NrSlaves) end),
    register(master, MasterPid),
    ok.

stop() ->
    master ! die,
    ok.

to_slave(Message, SlaveNr) ->
    master ! {to_slave, Message, SlaveNr},
    ok.

slave_pid_to_nr(SlavePid, SlavePids) ->
    slave_pid_to_nr(SlavePid, SlavePids, 1).

slave_pid_to_nr(SlavePid, [SlavePid | _Tail], SlaveNr) ->
    SlaveNr;

slave_pid_to_nr(SlavePid, [_Head | Tail], SlaveNr) ->
    slave_pid_to_nr(SlavePid, Tail, SlaveNr + 1).

slave_change_pid(OldSlavePid, NewSlavePid, SlavePids) ->
    lists:map(
      fun(Pid) ->
          if
              Pid == OldSlavePid ->
                  NewSlavePid;
              true ->
                  Pid
          end
      end,
      SlavePids
    ).

master_start(NrSlaves) ->
    process_flag(trap_exit, true),
    io:format("master: started~n", []),
    SlavePids = [spawn_link(fun() -> slave_start(SlaveNr) end) || SlaveNr <- lists:seq(1, NrSlaves)],
    master_loop(SlavePids).

master_loop(SlavePids) ->
    receive
        die ->
            io:format("master: received die~n"),
            lists:foreach(fun(SlavePid) -> SlavePid ! die end, SlavePids);
        {to_slave, Message, SlaveNr} ->
            io:format("master: forward ~p to slave ~p~n", [Message, SlaveNr]),
            SlavePid = lists:nth(SlaveNr, SlavePids),
            SlavePid ! Message,
            master_loop(SlavePids);
        {'EXIT', SlavePid, _Reason} ->
            SlaveNr = slave_pid_to_nr(SlavePid, SlavePids),
            io:format("master: slave ~p died~n", [SlaveNr]),
            NewSlavePid = spawn_link(fun() -> slave_start(SlaveNr) end),
            NewSlavePids = slave_change_pid(SlavePid, NewSlavePid, SlavePids),
            master_loop(NewSlavePids)
    end.

slave_start(SlaveNr) ->
    io:format("slave ~p: started~n", [SlaveNr]),
    slave_loop(SlaveNr).

slave_loop(SlaveNr) ->
    receive
        die ->
            io:format("slave ~p: received die~n", [SlaveNr]);
        Message ->
            io:format("slave ~p: received ~p~n", [SlaveNr, Message]),
            slave_loop(SlaveNr)
    end.

Erlang.org course exercises for spawning processes and exchanging messages

The Erlang.org website contains a number of programming exercises dealing with spawning processes and exchanging messages between them:

Write a function which starts 2 processes, and sends a message M times forwards and backwards between them. After the messages have been sent the processes should terminate gracefully.

%% Erlang exercises: Interaction between processes and concurrency, problem number 1. 
%%
%% Write a function which starts 2 processes, and sends a message M times forewards and backwards between them. 
%% After the messages have been sent the processes should terminate gracefully.
%%
%% See http://erlang.org/course/exercises.html for details.

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

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

solve() ->
    solve(10).

solve(NrMsgs) ->
    Pid1 = spawn(fun() -> process_1() end),
    spawn(fun() -> process_2(Pid1, NrMsgs) end),
    ok.

process_1() ->
    io:format("Process 1 starts.~n"),
    process_1_loop(),
    io:format("Process 1 ends.~n").

process_1_loop() ->
    receive
        {From, {message, More}} ->
            io:format("Process 1 received message ~p.~n", [More]),
            io:format("Process 1 sends message_reply.~n"),
            From ! {self(), {message_reply}},
            if
                More ->
                    process_1_loop();
                true ->
                    ok
            end
    end.

process_2(Pid1, NrMsgs) ->
    io:format("Process 2 starts.~n"),
    process_2_loop(Pid1, 1, NrMsgs),
    io:format("Process 2 ends.~n").

process_2_loop(Pid1, MsgNr, NrMsgs) ->
    io:format("Process 2 sends message nr ~p.~n", [MsgNr]),
    More = (MsgNr < NrMsgs),
    Pid1 ! {self(), {message, More}},
    receive
        {Pid1, {message_reply}} ->
            io:format("Process 2 received message_reply.~n"),
            if
                More ->
                    process_2_loop(Pid1, MsgNr + 1, NrMsgs);
                true ->
                    ok
            end
    end.

Write a function which starts N processes in a ring, and sends a message M times around all the processes in the ring. After the messages have been sent the processes should terminate gracefully.

%% Erlang exercises: Interaction between processes and concurrency, problem number 2. 
%%
%% Write a function which starts N processes in a ring, and sends a message M times around all the processes in the 
%% ring. After the messages have been sent the processes should terminate gracefully.
%%
%% See http://erlang.org/course/exercises.html for details.

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

-export([solve/0, solve/2]).

solve() ->
    solve(3, 2).

solve(NrProcesses, NrLoops) ->
    Pids = [spawn(fun() -> process_init(ProcessNr, NrProcesses) end) || ProcessNr <- lists:seq(1, NrProcesses)],
    [FirstPid | _] = Pids,
    set_next_pids(FirstPid, Pids),
    FirstPid ! {message, 1, NrLoops}.

set_next_pids(FirstPid, [Pid1, Pid2 | OtherPids]) ->
    Pid1 ! {set_next_pid, Pid2},
    set_next_pids(FirstPid, [Pid2 | OtherPids]);

set_next_pids(FirstPid, [LastPid]) ->
    LastPid ! {set_next_pid, FirstPid}.

process_init(ProcessNr, NrProcesses) ->
    io:format("Process ~p of ~p: waiting for set_next_pid message~n", [ProcessNr, NrProcesses]),
    receive
        {set_next_pid, NextPid} -> ok
    end,
    io:format("Process ~p of ~p: next pid is ~p~n", [ProcessNr, NrProcesses, NextPid]),
    process_loop(ProcessNr, NrProcesses, NextPid).

process_loop(ProcessNr, NrProcesses, NextPid) ->
    receive
        {message, Loop, NrLoops} ->
            io:format("Process ~p of ~p: receive message with loop ~p of ~p~n", [ProcessNr, NrProcesses, Loop, NrLoops]),
            if 
                ProcessNr == NrProcesses ->
                    NewLoop = Loop + 1;
                true ->
                    NewLoop = Loop
            end,
            NextPid ! {message, NewLoop, NrLoops},
            if 
                Loop < NrLoops ->
                    process_loop(ProcessNr, NrProcesses, NextPid);
                true ->
                    io:format("Process ~p: ends~n", [ProcessNr]),
                    ok
            end
    end.

Write a function which starts N processes in a star, and sends a message to each of them M times. After the messages have been sent the processes should terminate gracefully.

%% Erlang exercises: Interaction between processes and concurrency, problem number 3. 
%%
%% Write a function which starts N processes in a star, and sends a message to each of them M times. After the messages 
%% have been sent the processes should terminate gracefully.
%%
%% See http://erlang.org/course/exercises.html for details.

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

-export([solve/0, solve/2]).

solve() ->
    solve(3, 2).

solve(NrProcesses, NrLoops) ->
    SpokePids = [spawn(fun() -> spoke_process_start(ProcessNr) end) || ProcessNr <- lists:seq(1, NrProcesses)],
    spawn_link(fun() -> hub_process_start(SpokePids, NrLoops) end),
    ok.

spoke_process_start(ProcessNr) ->
    io:format("spoke_process ~p: start~n", [ProcessNr]),
    spoke_process_loop(ProcessNr).

spoke_process_loop(ProcessNr) ->
    receive
        {From, ping_request, More} ->
            io:format("spoke_process ~p: receive ping_request~n", [ProcessNr]),
            io:format("spoke_process ~p: send ping_reply~n", [ProcessNr]),
            From ! {self(), ping_reply}
    end,
    if
        More ->
            spoke_process_loop(ProcessNr);
        true ->
            io:format("spoke_process ~p: end~n", [ProcessNr]),
            ok
    end.

hub_process_start(SpokePids, NrLoops) ->
    io:format("hub_process: start~n"),
    hub_process_loop(SpokePids, NrLoops).

hub_process_loop(_SpokePids, 0) ->
    io:format("hub_process: end~n"),
    ok;

hub_process_loop(SpokePids, LoopNr) ->
    More = (LoopNr > 1),
    io:format("hub_process: loop ~p~n", [LoopNr]),
    ping_all_spokes(SpokePids, More),
    hub_process_loop(SpokePids, LoopNr - 1).

ping_all_spokes([], _More) ->
    ok;

ping_all_spokes([SpokePid | RemainingSpokePids], More) ->
    ping_spoke(SpokePid, More),
    ping_all_spokes(RemainingSpokePids, More).

ping_spoke(SpokePid, More) ->
    io:format("hub_process: send ping_request spoke ~p~n", [SpokePid]),
    SpokePid ! {self(), ping_request, More},
    receive
        {From, ping_reply} ->
            io:format("hub_process: receive ping_reply from spoke ~p~n", [From])
    end,
    ok.

Erlang solutions for Euler problems 19, 24, 25 and 48.

Solving project Euler problems has been fun and useful to learn the basics of sequential programming in Erlang and to get used to heavy emphasis on tail-recursion in Erlang.

However, the programs for solving Euler problems tend to use only a very small subset of the Erlang features: they generally don't use binaries, don't spawn processes, don't send messages, don't have error handling, don't use mnesia, etc.

I will continue to work on Euler problems in the background (because they are fun) but to take my learning of Erlang to the next level I have chosen a different set of exercises, namely the ones which are listed in the exercises section of the Erlang website.

Below are the Erlang programs for Euler problem numbers 19, 24, 25 and 48. This brings me to a grand total of 25 solved Euler problems and gives me bragging rights for reaching "Level 1".

While working on Euler problem 67 I discovered what I think is a bug in function io:fread. I posted this bug on stack overflow and on the erlang mailing list, but I haven't had any response yet.

Code for Erlang problem 19:

%% Project Euler, problem 19
%% 
%% How many Sundays fell on the first of the month during the twentieth century?

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

-export([solve/0]).

is_leap_year(Year) ->
    if
        Year rem 400 == 0 ->
            true;
        Year rem 100 == 0 ->
            false;
        Year rem 4 == 0 ->
            true;
        true ->
            false
    end.

days_in_month(Month, Year) ->
    case Month of
        1 -> 31;
        2 ->
            case is_leap_year(Year) of 
                true -> 29;
                false -> 28
            end;
        3 -> 31;
        4 -> 30;
        5 -> 31;
        6 -> 30;
        7 -> 31;
        8 -> 31;
        9 -> 30;
        10 -> 31;
        11 -> 30;
        12 -> 31
    end.

next_date({Day, Month, Year, Dow}) ->
    NewDow = (Dow + 1) rem 7,
    case Day == days_in_month(Month, Year) of
        false ->
            NewDay = Day + 1,
            NewMonth = Month,
            NewYear = Year;
        true ->
            case Month == 12 of
                false ->
                    NewDay = 1,
                    NewMonth = Month + 1,
                    NewYear = Year;
                true ->
                    NewDay = 1,
                    NewMonth = 1,
                    NewYear = Year + 1
            end
    end,
    {NewDay, NewMonth, NewYear, NewDow}.

is_first_of_month_sunday({Day, _Month, _Year, Dow}) ->
    (Day == 1) and (Dow == 0).

solve() ->
    solve({1, 1, 1900, 1}, 0).

solve(Date = {_Day, _Month, Year, _Dow}, Count) ->
    NextDate = next_date(Date),
    if
        Year < 1901 ->                         % Not in 20th century yet
            solve(NextDate, Count);
        Year =< 2000 ->
            case is_first_of_month_sunday(Date) of
                false -> NewCount = Count;
                true -> NewCount = Count + 1
            end,
            solve(NextDate, NewCount);
        true ->
            Count
    end.

Code for Erlang problem 24:

%% Project Euler, problem 24
%% 
%% What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
%%
%% Note that we compute ALL permutations of the 10 digits even though we only need the first million. I can't figure
%% out an easy way to "break off the comprehension early" and I thought the code using comprehension was too elegant
%% to pass up. This algorithm still finishes well within the allowed 1 minute.

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

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

permutations([]) -> [[]];
permutations(L) -> [[H|T] || H <- L, T <- permutations(L--[H])]. 

solve() -> lists:nth(1000000, permutations("0123456789")).

Code for Erlang problem 25:

%% Project Euler, problem 25
%% 
%% What is the first term in the Fibonacci sequence to contain 1000 digits?

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

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

nr_digits(N) ->
    if 
        N < 10 ->
            1;
        true ->
            1 + nr_digits(N div 10)
    end.

fibonacci(WantedDigits) ->
    fibonacci(WantedDigits, 1, 1, 2).

fibonacci(WantedDigits, Prev, Current, Term) ->
    NrDigits = nr_digits(Current),
    if
        NrDigits >= WantedDigits ->
            Term;
        true ->
            fibonacci(WantedDigits, Current, Prev + Current, Term + 1)
    end.

solve() ->
    solve(1000).

solve(WantedDigits) ->
    fibonacci(WantedDigits).

Code for Erlang problem 48:

%% Project Euler, problem 48
%% 
%% Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.

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

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

last_ten_digits(N) -> N rem 10000000000.

n_pow_n(N) -> n_pow_n(N, N).
n_pow_n(N, 1) -> N;
n_pow_n(N, Rem) -> N * n_pow_n(N, Rem-1).

sum_of_powers(Max) -> lists:sum([n_pow_n(N) || N <- lists:seq(1, Max)]).

solve() ->
    solve(1000).

solve(Max) ->
    last_ten_digits(sum_of_powers(Max)).

Erlang solution for Euler problem 23

In project Euler problem number 23 we are asked to find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

In the problem description we are told that we only need to try the numbers up to 28123.

The function sum_of_divisors(N) to determine the sum of the proper divisors of a number N has been used before, more recently in project Euler problem number 21.

Once we have sum_of_divisors/1, the function is_abundant(N) which determines whether a given number N is an abundant number is trivial to write.

This, in turn, allows us to write all_abundant_numbers_up_to(Max) which computes the list of all abundant numbers up to and including Max in order of increasing value. We use this function to compute all abundant number up to 28123.

The next step is to write function all_pairs_of_abundant_numbers_up_to(Max) which computes a list of which contains all numbers N which satisfy the following two conditions:

1. N = N1 + N2 where N1 and N2 are both amicable numbers.
2. N <= Max.

The next step is to write a function all_non_pairs_up_to(Max) which generates a list of numbers up to and including Max which are not a sum of two amicable numbers. We do this by sorting the list we generated in the previous step and finding all "holes" in the list. Note that we have to deal with the fact that the sorted list contains dupplicates.

Putting it all together we end up with the following Erlang program. Note that we make extensive use of list comprehensions.

The run time of this implementation (on my MacBook Pro) is 41 seconds which is only barely within the allowed one minute. That, along with the rather complex structure of the program, makes me think there is a short-cut which I missed. After punching in my correct solution I browsed the message board for problem 23. It turns out there is a much faster way to find the sum of factors which only loops to sqrt(N) instead of N/2.

%% Project Euler, problem 23
%% 
%% Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

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

-export([solve/0]).

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_abundant(N) ->
    sum_of_divisors(N) > N.

all_abundant_numbers_up_to(Max) ->
    [ N || N <- lists:seq(1, Max), is_abundant(N) ].

all_pairs_of_abundant_numbers_up_to(Max) ->
    AbundantNumbers = all_abundant_numbers_up_to(Max),
    [ N1 + N2 || N1 <- AbundantNumbers, N2 <- AbundantNumbers, N1 + N2 =< Max ].

all_non_pairs_up_to(Max) ->
    Pairs = all_pairs_of_abundant_numbers_up_to(Max),
    SortedPairs = lists:sort(Pairs),
    holes_in_list([ 0 | SortedPairs]).

holes_in_list([H1, H2 | Tail]) when H2 > H1 + 1 ->
    lists:seq(H1 + 1, H2 - 1) ++ holes_in_list([H2 | Tail]);
holes_in_list([_H1, H2 | Tail]) ->
    holes_in_list([H2 | Tail]);
holes_in_list(_List) ->
    [].

solve() -> 
    lists:sum(all_non_pairs_up_to(28123)).

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).

Erlang solution for Euler problem 20

Project Euler problem number 20 in which we are asked to find the sum of the digits of 100! is not particularly exiting, so here without further ado is my solution in Erlang:

%% Project Euler, problem 20
%% 
%% Find the sum of digits in 100!

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

-export([solve/0]).

fact(0) -> 1;
fact(N) -> N * fact(N-1).

sum_of_digits(N) when N < 10 -> N;
sum_of_digits(N) -> (N rem 10) + sum_of_digits(N div 10).

solve() ->
    solve(100).

solve(N) ->
    sum_of_digits(fact(N)).

Erlang solution for Euler problem 18

In project Euler problem number 18 we are asked to determine the maximum sum traveling from the top of a triangle to the base.

This time, I did not solve the problem using the brute-force approach of trying all possible roots from the top to the bottom.

Instead, I rely on the observation that the cost from a to the bottom = cost from a to the bottom + max(cost from b to the bottom, cost from c to the bottom):

   x
  x x
 x x x
a x x x
b c x x x
x x x x x x

This is used to "collapse" the bottom two rows of the triangle into one as follows:

   x                         x
  x x                       x x
 x x x         ==>         x x x
x x x x                   x x x x
a x x x x                 d x x x x
b c x x x x

where d = a + max(b,c).

This process is repeated until there is one remaining row which contains the answer.

In Erlang this is implemented as follows:

%% Project Euler, problem 18
%%
%% Find the maximum sum travelling from the top of the triangle to the base.

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

-export([solve/0]).

-define(TRIANGLE, [[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23],
                   [63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
                     [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
                       [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
                         [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
                           [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
                             [41, 41, 26, 56, 83, 40, 80, 70, 33],
                               [99, 65, 04, 28, 06, 16, 70, 92],
                                 [88, 02, 77, 73, 07, 63, 67],
                                   [19, 01, 23, 75, 03, 34],
                                     [20, 04, 82, 47, 65],
                                       [18, 35, 87, 10],
                                         [17, 47, 82],
                                           [95, 64],
                                             [75]].

% Reduce the triangle to a smaller triangle by collapsing the 1st and 2nd row into one.
% If we have collapsed the triangle to a single row with one number, we are done.
%
collapse_triangle([[N]]) ->
  N;
collapse_triangle([FirstRow, SecondRow | RemainingRows]) ->
  CollapsedRow = collapse_rows(FirstRow, SecondRow),
  collapse_triangle([CollapsedRow | RemainingRows]).

% Collapse two rows into one as follows:
%    A B
%     C  --> C' = C + max(A,B)
% When the first row is reduced to a single number, we are done.
%
collapse_rows([_A], []) ->
  [];
collapse_rows([A, B | Tail1], [C | Tail2]) ->
  [C + max(A, B)] ++ collapse_rows([B | Tail1], Tail2).

max(A, B) ->
  if
      A > B ->
          A;
      true ->
          B
  end.
    
solve() ->
  collapse_triangle(?TRIANGLE).

Erlang solution for Euler problem 17

In project Euler problem number 17 we are asked to determine how many letters would be needed to write all the numbers in words from 1 to 1000?

The following Erlang program solves this in a straightforward manner.

We could have taken some short cuts (we don't actually have to generate the words for each number) but I did it the long way because this is an exercise to learn Erlang.

%% Project Euler, problem 17
%% 
%% What is the sum of the digits of the number 2^1000?

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

-export([solve/0, solve/1, number_to_string/1, count_letters/1, count_letters_in_number/1]).

-define(SPACE, $\ ).

number_to_string(N) ->
    if
        N == 0 -> "zero";
        N == 1 -> "one";
        N == 2 -> "two";
        N == 3 -> "three";
        N == 4 -> "four";
        N == 5 -> "five";
        N == 6 -> "six";
        N == 7 -> "seven";
        N == 8 -> "eight";
        N == 9 -> "nine";
        N == 10 -> "ten";
        N == 11 -> "eleven";
        N == 12 -> "twelve";
        N == 13 -> "thirteen";
        N == 14 -> "fourteen";
        N == 15 -> "fifteen";
        N == 16 -> "sixteen";
        N == 17 -> "seventeen";
        N == 18 -> "eighteen";
        N == 19 -> "nineteen";
        N == 20 -> "twenty";
        N == 30 -> "thirty";
        N == 40 -> "forty";
        N == 50 -> "fifty";
        N == 60 -> "sixty";
        N == 70 -> "seventy";
        N == 80 -> "eighty";
        N == 90 -> "ninety";
        N < 100 -> number_to_string(N div 10 * 10) ++ "-" ++ number_to_string(N rem 10);
        N < 1000 -> 
            Hundreds = number_to_string(N div 100) ++ " hundred",
            if 
                (N rem 100) == 0 ->
                    Hundreds;
                true ->
                    Hundreds ++ " and " ++ number_to_string(N rem 100)
            end;
        N == 1000 -> "one thousand"
    end.

count_letters([]) ->
    0;
count_letters([H|T]) ->
    if
        (H == ?SPACE) or (H == $-) ->
            count_letters(T);
        true ->
            1 + count_letters(T)
    end.

count_letters_in_number(N) ->
    count_letters(number_to_string(N)).

solve() ->
    solve(1000).

solve(0) ->
    0;
solve(N) ->
    count_letters_in_number(N) + solve(N-1).

Erlang solution for Euler problem 16

In project Euler problem number 16 we are asked to sum the digits of the number 2^1000.

The Erlang solution for this one is trivial, thanks to the arbitrary precision integer support in Erlang:

%% Project Euler, problem 16
%% 
%% What is the sum of the digits of the number 2^1000?

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

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

power_of_2(N) ->
    1 bsl N.

digits_sum(N) ->
    if 
        N < 10 ->
            N;
        true ->
            (N rem 10) + digits_sum(N div 10)
    end.

solve() ->
    solve(1000).

solve(N) ->
    digits_sum(power_of_2(N)).

Erlang solution for Euler problem 15

In project Euler problem number 15 we are asked to determine the number of routes (without backtracking) from corner to corner in a 20 x 20 grid.

My first attempt to solve this (see code for approach A below) used a straight-forward recursive brute-force approach based on the observation the the number routes R to get from corner to corner in a rectange of size (X,Y) obeys the following relation: R(X,Y) = R(X-1,Y) + R(X,Y-1) with the boundary conditions R(X,0) = 1 and R(0,Y) = 1.

The program for approach A produces the correct answers. However, the run-time increased so rapidly with the problem size that it was hopeless to compute the answer for a 20 x 20 grid within a minute. The following shows the graph of the run-time versus the grid size.
My second attempt (see code for approach B below) is based on the observation that approach A ends up computing the answer for R(X,Y) not just once but many times during the recursion. To avoid that, we store the answer for R(X,Y) in a dictionary the first time it is computed. If we need the answer again, we retrieve the answer from the dictionary thereby avoiding another deep recursion. This approach computed R(20,20) in less than 2 milliseconds on my Apple MacBook Pro.

P.S.: After reading the notes for the problem, I realized there is a much more elegant way to solve this problem. I won't spoil it by giving that answer away.

Code for approach A:

%% Project Euler, problem 15
%%
%% Find number of corner-to-corner routes (without backtracking) in a 20x20 grid

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

-export([solve/0, solve/1, routes_in_grid/2]).

routes_in_grid(X, Y) ->
   if
       (X == 0) or (Y == 0) ->
           1;
       true ->
           routes_in_grid(X - 1, Y) + routes_in_grid(X, Y - 1)
   end.
  
solve() ->
   solve(20).

solve(N) ->
   routes_in_grid(N, N).

Code for approach B:

%% Project Euler, problem 15
%%
%% Find number of corner-to-corner routes (without backtracking) in a 20x20 grid

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

-export([solve/0, solve/1, routes_in_grid/2]).

routes_in_grid(X, Y) ->
   Solutions = dict:new(),
   {Routes, _} = routes_in_grid(X, Y, Solutions),
   Routes.

routes_in_grid(0, _Y, Solutions) ->
   {1, Solutions};

routes_in_grid(_X, 0, Solutions) ->
   {1, Solutions};

routes_in_grid(X, Y, Solutions) ->
   case dict:find({X, Y}, Solutions) of
       {ok, Routes} ->
           {Routes, Solutions};
       error ->
           {Routes1, Solutions1} = routes_in_grid(X - 1, Y, Solutions),
           {Routes2, Solutions2} = routes_in_grid(X, Y - 1, Solutions1),
           NewRoutes = Routes1 + Routes2,
           NewSolutions = dict:store({X, Y}, NewRoutes, Solutions2),
           {NewRoutes, NewSolutions}
   end.

solve() ->
   solve(20).

solve(N) ->
   routes_in_grid(N, N).

Erlang solution for Euler problem 14

In project Euler problem number 14 we are asked to find the longest Collatz sequence using a starting number under one million.

The code for the straight-forward brute force approach (which executes in 9.6 seconds on my MacBook Pro) is:

%% Project Euler, problem 14
%% 
%% Find the longest sequence using a starting number under one million.

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

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

next_in_series(Nr) ->
    if
        Nr rem 2 == 0 ->
            Nr div 2;
        true ->
            3 * Nr + 1
    end.

series_length(StartNr) ->
    if
        StartNr == 1 ->
            1;
        true ->
            1 + series_length(next_in_series(StartNr))
    end.

longest_series(MaxStartNr) ->
    longest_series(1, MaxStartNr, 0, 0).
    
longest_series(StartNr, MaxStartNr, Longest, LongestStartNr) ->
    if
        StartNr >= MaxStartNr ->
            LongestStartNr;
        true ->
            Length = series_length(StartNr),
            if
                Length > Longest ->
                    longest_series(StartNr + 1, MaxStartNr, Length, StartNr);
                true ->
                    longest_series(StartNr + 1, MaxStartNr, Longest, LongestStartNr)
            end
    end.

solve() ->
    solve(1000000).

solve(N) ->
    longest_series(N).

Erlang solution for Euler problem 13

Project Euler problem number 13 is an easy one: we are asked to find the first ten digits of the sum of one hundred 50-digit numbers. Since Erlang supports arbitrary precision integers, it is simple to simply add the numbers and get the first 10 digits.

%% Project Euler, problem 13
%% 
%% Find the first ten digits of the sum of one-hundred 50-digit numbers.

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

-export([solve/0]).

-define(NUMBERS, [37107287533902102798797998220837590246510135740250,
                  46376937677490009712648124896970078050417018260538,
                  74324986199524741059474233309513058123726617309629,
                  91942213363574161572522430563301811072406154908250,
                  23067588207539346171171980310421047513778063246676,
                  89261670696623633820136378418383684178734361726757,
                  28112879812849979408065481931592621691275889832738,
                  44274228917432520321923589422876796487670272189318,
                  47451445736001306439091167216856844588711603153276,
                  70386486105843025439939619828917593665686757934951,
                  62176457141856560629502157223196586755079324193331,
                  64906352462741904929101432445813822663347944758178,
                  92575867718337217661963751590579239728245598838407,
                  58203565325359399008402633568948830189458628227828,
                  80181199384826282014278194139940567587151170094390,
                  35398664372827112653829987240784473053190104293586,
                  86515506006295864861532075273371959191420517255829,
                  71693888707715466499115593487603532921714970056938,
                  54370070576826684624621495650076471787294438377604,
                  53282654108756828443191190634694037855217779295145,
                  36123272525000296071075082563815656710885258350721,
                  45876576172410976447339110607218265236877223636045,
                  17423706905851860660448207621209813287860733969412,
                  81142660418086830619328460811191061556940512689692,
                  51934325451728388641918047049293215058642563049483,
                  62467221648435076201727918039944693004732956340691,
                  15732444386908125794514089057706229429197107928209,
                  55037687525678773091862540744969844508330393682126,
                  18336384825330154686196124348767681297534375946515,
                  80386287592878490201521685554828717201219257766954,
                  78182833757993103614740356856449095527097864797581,
                  16726320100436897842553539920931837441497806860984,
                  48403098129077791799088218795327364475675590848030,
                  87086987551392711854517078544161852424320693150332,
                  59959406895756536782107074926966537676326235447210,
                  69793950679652694742597709739166693763042633987085,
                  41052684708299085211399427365734116182760315001271,
                  65378607361501080857009149939512557028198746004375,
                  35829035317434717326932123578154982629742552737307,
                  94953759765105305946966067683156574377167401875275,
                  88902802571733229619176668713819931811048770190271,
                  25267680276078003013678680992525463401061632866526,
                  36270218540497705585629946580636237993140746255962,
                  24074486908231174977792365466257246923322810917141,
                  91430288197103288597806669760892938638285025333403,
                  34413065578016127815921815005561868836468420090470,
                  23053081172816430487623791969842487255036638784583,
                  11487696932154902810424020138335124462181441773470,
                  63783299490636259666498587618221225225512486764533,
                  67720186971698544312419572409913959008952310058822,
                  95548255300263520781532296796249481641953868218774,
                  76085327132285723110424803456124867697064507995236,
                  37774242535411291684276865538926205024910326572967,
                  23701913275725675285653248258265463092207058596522,
                  29798860272258331913126375147341994889534765745501,
                  18495701454879288984856827726077713721403798879715,
                  38298203783031473527721580348144513491373226651381,
                  34829543829199918180278916522431027392251122869539,
                  40957953066405232632538044100059654939159879593635,
                  29746152185502371307642255121183693803580388584903,
                  41698116222072977186158236678424689157993532961922,
                  62467957194401269043877107275048102390895523597457,
                  23189706772547915061505504953922979530901129967519,
                  86188088225875314529584099251203829009407770775672,
                  11306739708304724483816533873502340845647058077308,
                  82959174767140363198008187129011875491310547126581,
                  97623331044818386269515456334926366572897563400500,
                  42846280183517070527831839425882145521227251250327,
                  55121603546981200581762165212827652751691296897789,
                  32238195734329339946437501907836945765883352399886,
                  75506164965184775180738168837861091527357929701337,
                  62177842752192623401942399639168044983993173312731,
                  32924185707147349566916674687634660915035914677504,
                  99518671430235219628894890102423325116913619626622,
                  73267460800591547471830798392868535206946944540724,
                  76841822524674417161514036427982273348055556214818,
                  97142617910342598647204516893989422179826088076852,
                  87783646182799346313767754307809363333018982642090,
                  10848802521674670883215120185883543223812876952786,
                  71329612474782464538636993009049310363619763878039,
                  62184073572399794223406235393808339651327408011116,
                  66627891981488087797941876876144230030984490851411,
                  60661826293682836764744779239180335110989069790714,
                  85786944089552990653640447425576083659976645795096,
                  66024396409905389607120198219976047599490197230297,
                  64913982680032973156037120041377903785566085089252,
                  16730939319872750275468906903707539413042652315011,
                  94809377245048795150954100921645863754710598436791,
                  78639167021187492431995700641917969777599028300699,
                  15368713711936614952811305876380278410754449733078,
                  40789923115535562561142322423255033685442488917353,
                  44889911501440648020369068063960672322193204149535,
                  41503128880339536053299340368006977710650566631954,
                  81234880673210146739058568557934581403627822703280,
                  82616570773948327592232845941706525094512325230608,
                  22918802058777319719839450180888072429661980811197,
                  77158542502016545090413245809786882778948721859617,
                  72107838435069186155435662884062257473692284509516,
                  20849603980134001723930671666823555245252804609722,
                  53503534226472524250874054075591789781264330331690]).

first_ten_digits(N) ->
    if
        N >= 10000000000 ->
            first_ten_digits(N div 10);
        true ->
            N
    end.

solve() ->
    first_ten_digits(lists:sum(?NUMBERS)).

Erlang solution for Euler problem 12

In project Euler problem 12 we are asked to find the value of the first triangle number to have over five hundred divisors.

I implemented a brute force approach which generates all triangle numbers. For each triangle number T, the program computes the number of divisors. When it finds the first triangle number to have more than N = 500 divisors, the program terminates.

My first implementation (the code is not show below) computed the number of divisors of a given triangle number T by trying to divide it by all numbers from 1 tru T. This allowed me to solve the problem, but the run-time was much more than the allowed one minute.

My second implementation (see "approach 1" below) only tried all numbers from 1 to sqrt(T). This is based on the observation that if T = x*y then one of the two factors (x or y) must be below sqrt(T) and and the other must be above sqrt(T). Thus, if we find a factor x below sqrt(T), we know there are two factors because there must be a corresponding factor y above sqrt(T). The code must be careful to count sqrt(T) only once as a factor if T happens to be a square number. This approach solved the problem in 2.8 seconds for N = 500.

Once I had submitted my solution to the project Euler website and got access to the problem notes, I discovered the existence of a more efficient method to compute the number of factors of a number which is called the Tau function. My third implementation (see "approach 2" below) used this approach. This approach was almost twice as fast when the required number of divisors N is 500. For greater number of divisors, the difference between approach 1 and 2 was greater as shown in the following graph.



The code for approach 1:

%% Project Euler, problem 12
%% 
%% What is the value of the first triangle number to have over five hundred divisors?

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

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

% Try only the divisors between 1 and sqrt(Number).
%
count_divisors(Number) ->
    Try = 1,
    MaxTry = trunc(math:sqrt(Number)),
    Count = 0,
    count_divisors(Number, Try, MaxTry, Count).

count_divisors(Number, Try, MaxTry, Count) ->
    if 
        Try > MaxTry ->
            Count;
        Number rem Try == 0 ->
            if 
                Try == MaxTry ->
                    Found = 1;
                true ->
                    Found = 2      % every divisor below sqrt(Number) has a counter-part above it
            end,
            count_divisors(Number, Try + 1, MaxTry, Count + Found);
        true ->
            count_divisors(Number, Try + 1, MaxTry, Count)
    end.

solve() ->
    solve(500).

solve(WantedFactors) ->
    solve(3, 3, 0, WantedFactors).

solve(Try, Step, BestSoFar, WantedFactors) ->
    Count = count_divisors(Try),
    if
        Count > BestSoFar ->
            NewBestSoFar = Count;
        true ->
            NewBestSoFar = BestSoFar
    end,
    case Count > WantedFactors of
        true ->
            Try;
        false ->
            solve(Try + Step, Step + 1, NewBestSoFar, WantedFactors)
    end.

The code for approach 2:

%% Project Euler, problem 12
%% 
%% What is the value of the first triangle number to have over five hundred divisors?
%%
%% Implementation uses the Tau function.
%% See http://mathschallenge.net/index.php?section=faq&ref=number/number_of_divisors for details.

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

-export([solve/0, solve/1, prime_factors/1, count_divisors/1, make_count_list/1]).

prime_factors(Number) ->
    prime_factors(Number, 2).

prime_factors(Number, Try) ->
    if
        Try > Number ->
            [];
        Number rem Try == 0 ->
            [Try | prime_factors(Number div Try, Try)];
        true ->
            prime_factors(Number, Try + 1)
    end.

make_count_list(List) ->
    make_count_list(List, []).

make_count_list([], Results) ->
    lists:reverse(Results);

make_count_list(List = [Head | _Tail], Results) ->
    {RemainingList, Count} = count_nr(List, Head),
    make_count_list(RemainingList, [Count | Results]).

count_nr(List = [Head | Tail], Nr) ->
    if 
        Head == Nr ->
            {RemainingList, Count} = count_nr(Tail, Nr),
            {RemainingList, Count + 1};
        true ->
            {List, 0}
    end;

count_nr([], _Nr) ->
    {[], 0}.

count_divisors(Number) ->
    CountList = make_count_list(prime_factors(Number)),
    lists:foldl(fun(Nr, Acc) -> Acc * (Nr + 1) end, 1, CountList).

solve() ->
    solve(500).

solve(WantedFactors) ->
    solve(1, 2, WantedFactors).

solve(Try, Step, WantedFactors) ->
    case count_divisors(Try) > WantedFactors of
        true ->
            Try;
        false ->
            solve(Try + Step, Step + 1, WantedFactors)
    end.

Erlang solution for Euler problem 11

In project Euler problem number 11 we are asked to find the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in a given 20 by 20 grid of numbers.

Once again, the problem is solved using the brute force method of simply trying all possible combinations of four adjacent numbers.

In previous assignment I tended to write recursion functions from scratch. In this assignment I tried to use lists and functions from the Erlang lists module (lists:seq, lists:map, and lists:max).

%% Project Euler, problem 11
%% 
%% What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) 
%% in the 20×20 grid given below?

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

-export([solve/0]).

-define(PRODUCT_SIZE, 4).
-define(GRID_SIZE, 20).
-define(GRID, [[08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08],
               [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00],
               [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65],
               [52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91],
               [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
               [24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
               [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
               [67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21],
               [24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
               [21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95],
               [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92],
               [16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57],
               [86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
               [19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40],
               [04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
               [88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
               [04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36],
               [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16],
               [20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54],
               [01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]]).

get_value(X, Y) ->
    lists:nth(X, lists:nth(Y, ?GRID)).

product(XStart, YStart, XDelta, YDelta) ->
    if
        XStart + ?PRODUCT_SIZE * XDelta - 1 > ?GRID_SIZE ->
            0;
        XStart + ?PRODUCT_SIZE * XDelta - 1 < 1 ->
            0;
        YStart + ?PRODUCT_SIZE * YDelta - 1 > ?GRID_SIZE ->
            0;
        YStart + ?PRODUCT_SIZE * YDelta - 1 < 1 ->
            0;
        true -> 
            product(XStart, YStart, XDelta, YDelta, ?PRODUCT_SIZE)
    end.

product(XStart, YStart, XDelta, YDelta, N) ->
    V = get_value(XStart, YStart),
    if
        N == 1 ->
            V;
        N > 1 ->
            V * product(XStart + XDelta, YStart + YDelta, XDelta, YDelta, N-1)
    end.

highest_product(X, Y) ->
    lists:max([product(X, Y, 1, 0),     % horizontal,
               product(X, Y, 0, 1),     % vertical,
               product(X, Y, 1, 1),     % diagonal down right
               product(X, Y, 1, -1)]).  % diagonal up right

highest_product(Y) ->
    lists:max(lists:map(fun(X) -> highest_product(X, Y) end, lists:seq(1, ?GRID_SIZE))).
                
highest_product() ->
    lists:max(lists:map(fun(Y) -> highest_product(Y) end, lists:seq(1, ?GRID_SIZE))).
                
solve() ->
    highest_product().

Erlang solution for Euler problem 10

In Euler problem 10 we are asked to compute the sum of all prime numbers below N, where N is 2 million.

I've implemented this in Erlang using four different approaches.

The first approach (see module euler10a below) visits every odd number between two and two million. It checks whether a number n is a prime by trying to divide it by every odd number between 2 and sqrt(n).

The second approach (see module euler10b below) uses an implementation which is remarkably elegant in Erlang and which is often incorrectly described as being an implementation of the sieve of Eratosthenes. The code for this approach is taken from an answer by Andreas Jacobsen to this stack overflow question. The excellent article "The Genuine Sieve of Eratosthenes" by Melissa O'Neill describes why this approach is actually not an implementation of the sieve of Eratosthenes, how that causes it to be extremely inefficient, and how it can be modified to be more efficient. I've included this implementation because of the sheer elegance of the code.

The third approach (see module 10c below) is a simple implementation of the sieve of Eratosthenes using the the Erlang array module.

The fourth approach (see module 10e below) is an optimized implementation of the sieve of Eratosthenes. The main difference with the third approach is that it only stores odd numbers in the array.

All of these approaches are single threaded. I would like to do some more research into distributed algorithms for finding prime numbers and implement a concurrent solution in Erlang.

The following shows the run-time of each of these algorithms (on an Apple MacBook Pro) in seconds as a function of the size of the problem N.



Source code for approach A:

%% Project Euler, problem 10
%% 
%% Find the sum of all the primes below two million.
%%
%% Approach a:
%% - Try all odd numbers from below two million.
%% - Check each number n for being a prime, by trying to devide it by all odd number 3 ... sqrt(n). 

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

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

isPrime(N) ->
    MaxTry = trunc(math:sqrt(N)),
    isPrime(N, 3, MaxTry).

isPrime(N, Try, MaxTry) ->
    if 
        Try > MaxTry ->
            true;
        true ->
            if
                N rem Try == 0 -> 
                    false;
                true ->
                    isPrime(N, Try+2, MaxTry)
            end
    end.

sumPrimes(Max) ->
    sumPrimes(3, 2, Max).

sumPrimes(Current, Sum, Max) ->
    if
        Current >= Max ->
            Sum;
        true ->
            case isPrime(Current) of
                true -> NewSum = Sum + Current;
                false -> NewSum = Sum
            end,
            sumPrimes(Current+2, NewSum, Max)
    end.

solve() ->
    solve(2000000).

solve(N) ->
    sumPrimes(N).

Source code for approach B:

%% Project Euler, problem 10
%% 
%% Find the sum of all the primes below two million.
%%
%% Approach b:
%% - Generate all primes below two million, using an extremely elegant but highly inefficient algorithm which is
%%   similar but not quite identical to the sieve of Eratosthenes.
%% - Sum the generated primes. 

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

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

sieve([]) ->
    [];

sieve([H|T]) ->                  
    List = lists:filter(fun(N) -> N rem H /= 0 end, T),
    [H|sieve(List)];

sieve(N) ->
    sieve(lists:seq(2, N)).

sum(L) ->
    lists:foldl(fun (N, Acc) -> N + Acc end, 0, L).

solve() ->
    solve(2000000).

solve(N) ->
    sum(sieve(N)).

Source code for approach C:

%% Project Euler, problem 10
%% 
%% Find the sum of all the primes below two million.
%%
%% Approach c:
%% - Generate all primes below two million, using the sieve of Eratosthenes implemented using arrays.
%% - Sum the generated primes. 

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

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

sieve(N) ->
    Array1 = array:new([{size, N+1}, {default, is_prime}]),    % +1 because array is 0-based
    Array2 = array:set(0, is_not_prime, Array1),               % handle 0 as a special case
    Array3 = array:set(1, is_not_prime, Array2),               % handle 1 as a special case
    MaxTry = trunc(math:sqrt(N)),
    Try = 2,                                                   % start with 2 as the first candidate prime
    sieve(Array3, MaxTry, Try).

sieve(Array, MaxTry, Try) ->
    case Try > MaxTry of
        true ->
            Array;
        false ->
            case array:get(Try, Array) of
                is_not_prime ->
                    sieve(Array, MaxTry, Try + 1);
                is_prime ->
                    NewArray = remove_multiples_of_prime(Array, Try),
                    sieve(NewArray, MaxTry, Try + 1)
            end
    end.

remove_multiples_of_prime(Array, Prime) ->
    Multiple = 2 * Prime,
    remove_multiples_of_prime(Array, Prime, Multiple).

remove_multiples_of_prime(Array, Prime, Multiple) ->
    case Multiple >= array:size(Array) of
        true -> 
            Array;
        false ->
            NewArray = array:set(Multiple, is_not_prime, Array),
            remove_multiples_of_prime(NewArray, Prime, Multiple + Prime)
    end.
    
sum(Array) ->
    array:foldl(
        fun (Index, Value, Acc) -> 
            if 
                Value == is_prime ->
                    Acc + Index;
                true ->
                    Acc
            end
        end, 
        0, 
        Array
    ).

solve() ->
    solve(2000000).

solve(N) ->
    sum(sieve(N)).

Source code for approach E:

%% Project Euler, problem 10
%% 
%% Find the sum of all the primes below two million.
%%
%% Approach e:
%% - Generate all primes below two million, using the sieve of Eratosthenes implemented using arrays.
%% - Only store odd numbers in the sieve array.
%% - Sum the generated primes. 

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

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

init_sieve_array(N) ->
    Size = (N + 1) div 2,                                      % only store odd numbers (0->1, 1->3, 2->5, etc.)
    Array1 = array:new([{size, Size}, {default, is_prime}]),
    Array2 = array:set(0, is_not_prime, Array1),               % handle 1 as a special case
    Array2.

get_value_from_sieve_array(Nr, Array) ->
    1 = Nr rem 2,                                              % Nr must be odd
    Index = Nr div 2,
    array:get(Index, Array).

set_value_in_sieve_array(Nr, Value, Array) ->
    1 = Nr rem 2,                                              % Nr must be odd
    Index = Nr div 2,
    array:set(Index, Value, Array).

sieve(N) ->
    Array = init_sieve_array(N),
    MaxTry = trunc(math:sqrt(N)),
    Try = 3,                                                   % start with 3 as the first real prime
    sieve(N, Array, MaxTry, Try).

sieve(N, Array, MaxTry, Try) ->
    case Try > MaxTry of
        true ->
            Array;
        false ->
            case get_value_from_sieve_array(Try, Array) of
                is_not_prime ->
                    sieve(N, Array, MaxTry, Try + 2);
                is_prime ->
                    NewArray = remove_multiples_of_prime(N, Array, Try),
                    sieve(N, NewArray, MaxTry, Try + 2)
            end
    end.

remove_multiples_of_prime(N, Array, Prime) ->
    Multiple = 3 * Prime,
    remove_multiples_of_prime(N, Array, Prime, Multiple).

remove_multiples_of_prime(N, Array, Prime, Multiple) ->
    case Multiple > N of
        true -> 
            Array;
        false ->
            NewArray = set_value_in_sieve_array(Multiple, is_not_prime, Array),
            remove_multiples_of_prime(N, NewArray, Prime, Multiple + 2*Prime)
    end.
    
sum(Array) ->
    Sum = array:foldl(
        fun (Index, Value, Acc) -> 
            if 
                Value == is_prime ->
                    Acc + (2 * Index) + 1;
                true ->
                    Acc
            end
        end, 
        0, 
        Array
    ),
    Sum + 2.                 % 2 is the only even number and is not in the array

solve() ->
    solve(2000000).

solve(N) ->
    sum(sieve(N)).

Erlang solution for Euler problem 9

In Euler problem 9 we are asked to find the one and only Pythagoran triplet for which a+b+c=1000.

We simply try all combinations of three numbers and check whether each is the solution we are looking for.

The main the complication is the order in which all combinations of three numbers are generated. The following example illustrates this:

1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5
1 2 6
1 3 6
2 3 6
1 4 6
2 4 6
3 4 6
1 5 6
2 5 6
...

Here is the corresponding Erlang program:

%% Project Euler, problem 9
%%
%% Find the greatest product of five consecutive digits in a given 1000-digit number.

%% A Pythagorean triplet is a set of three natural numbers, a < 2 =" c^2" 2 =" 9" 16 =" 25" c =" 1000.">
   (A*A + B*B == C*C) and (A + B + C == 1000).

solve(A,B,C) ->
   case isSolution(A,B,C) of
       true -> A * B * C;
       false ->
           if
               A+1 <>
                   solve(A+1, B, C);
               true ->
                   if
                       B+1 <>
                           solve (1, B+1, C);
                       true ->
                           solve (1, 2, C+1)
                   end
           end
   end.

solve() ->
   solve(1,2,3).

Erlang solution for Euler problem 8

Euler problem 8 asks us to find the greatest product of five consecutive digits in a given 1000-digit number.

Once again, we solve it using the obvious brute force method. The one interesting aspect of this problem is that it is the first problem in which we can make use of Erlang's list processing and pattern matching.

Here is my solution:

%% Project Euler, problem 8
%%
%% Find the greatest product of five consecutive digits in a given 1000-digit number.

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

-export([solve/0]).

-define(NUMBER, "73167176531330624919225119674426574742355349194934"
               "96983520312774506326239578318016984801869478851843"
               "85861560789112949495459501737958331952853208805511"
               "12540698747158523863050715693290963295227443043557"
               "66896648950445244523161731856403098711121722383113"
               "62229893423380308135336276614282806444486645238749"
               "30358907296290491560440772390713810515859307960866"
               "70172427121883998797908792274921901699720888093776"
               "65727333001053367881220235421809751254540594752243"
               "52584907711670556013604839586446706324415722155397"
               "53697817977846174064955149290862569321978468622482"
               "83972241375657056057490261407972968652414535100474"
               "82166370484403199890008895243450658541227588666881"
               "16427171479924442928230863465674813919123162824586"
               "17866458359124566529476545682848912883142607690042"
               "24219022671055626321111109370544217506941658960408"
               "07198403850962455444362981230987879927244284909188"
               "84580156166097919133875499200524063689912560717606"
               "05886116467109405077541002256983155200055935729725"
               "71636269561882670428252483600823257530420752963450").

stringToNumber([H|T]) ->
   [ H - $0 | stringToNumber(T) ];

stringToNumber([]) ->
   [].

findBiggestProductOf5Digits([A,B,C,D,E|T], BiggestProduct) ->
   Product = A * B * C * D * E,
   Rest = [B, C, D, E | T],
   if
       Product > BiggestProduct -> findBiggestProductOf5Digits(Rest, Product);
       true -> findBiggestProductOf5Digits(Rest, BiggestProduct)
   end;

findBiggestProductOf5Digits([_A,_B,_C,_D], BiggestProduct) ->
   BiggestProduct.

solve() ->
   findBiggestProductOf5Digits(stringToNumber(?NUMBER), 0).

Erlang solution for Euler problem 7

Euler problem 7 asks us to find the 10001^st prime number.

Once again, my Erlang solution uses the brute force approach with a few optimizations.

I check all odd numbers for being a prime number until I find the 10001^st prime.

To check whether number n is prime, I try to divide it by all numbers from 2 thru sqrt(n).

Here is the brute force Erlang program:

%% Project Euler, problem 7
%%
%% By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
%%
%% What is the 10001st prime number?

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

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

isPrime(N) ->
  MaxTry = trunc(math:sqrt(N)),
  isPrime(N, 2, MaxTry).

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

findNthPrime(PrimesNeeded) ->
  findNthPrime(PrimesNeeded, 3, 1, 2).      %% Treat 2 as a special case: it is the only even prime.

findNthPrime(PrimesNeeded, Try, PrimesFound, LastPrimeFound) ->
  if
      PrimesFound == PrimesNeeded ->
          LastPrimeFound;
      true ->
          case isPrime(Try) of
              true -> findNthPrime(PrimesNeeded, Try+2, PrimesFound+1, Try);
              false -> findNthPrime(PrimesNeeded, Try+2, PrimesFound, LastPrimeFound)
          end
  end.

solve() ->
  findNthPrime(10001).

I was aware of the sieve of Eratosthenes as a method to find all prime numbers up to some number n (which is not exactly the same question as Euler problem 7) but I did not know how to implement it in Erlang. It turns out that there there is a stack overflow question which discusses this and contains several example implementations. There is also this excellent article on implementing the sieve in functional languages.

Erlang solution for Euler problem 6

Euler problem 6 asks us to compute the difference between the sum of squares and the square of the sums for the numbers 1 ... 100.

I remembered the formula for adding up the integers from 1 to N from an amusing story about how Gauss solved it when he was 10 years old:

1 + 2 + 3 + ... + n = n(n+1)/2.

I did not remember a formula for the sum of squares, so I computed that brute force.

After I wrote the Erlang program I found that there is in fact a formula (the square pyramidal number which is a special case of Faulhaber's formula) for the sum of squares too:

1² + 2² + 3² + ... + n² = (2n³ + 3n² + n)/2

Here is the Erlang solution:

%% Project Euler, problem 6
%%
%% The sum of the squares of the first ten natural numbers is,
%% 1^2 + 2^2 + ... + 10^2 = 385
%% 
%% The square of the sum of the first ten natural numbers is,
%% (1 + 2 + ....+ 10)^2 = 55^2 =3025
%% 
%% Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum 
%% is 3025 - 385 = 2640.
%% 
%% Find the difference between the sum of the squares of the first one hundred natural numbers and the square of 
%% the sum.

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

-export([solve/0]).

sumOfSquares(N) ->
    if 
        N == 0 -> 0;
        true -> N * N + sumOfSquares(N-1)
    end.

squareOfSum(N) ->
    Sum = N * (N+1) div 2,
    Sum * Sum.

solve() ->
    solve(100).

solve(N) ->
    squareOfSum(N) - sumOfSquares(N).

Erlang solution for Euler problem 5

In project Euler problem number 5 we are asked to find the smallest number that is evenly divisible by all of the numbers from 1 to 20.

In the first 4 projects I chose the dumb brute force approach. This time I am going to make at least a token effort to introduce some optimizations.

The dumb brute force approach is to try all numbers, starting at 1, until you find a number which is divisible by 1 thru 20.

The first observation is that we don't have to try to divide by all number 1 tru 20. For example, if we try dividing by 20 we don't need to also try dividing by 5 because every number which is divisible by 20 is also divisible by 5. After some consideration, it becomes clear we only have to try dividing by 11 thru 20:

1 : don't check, every number is divisible by 1
2 : don't check, already covered by 20
3 : don't check, already covered by 18
4 : don't check, already covered by 20
5 : don't check, already covered by 20
6 : don't check, already covered by 18
7 : don't check, already covered by 14
8 : don't check, already covered by 16
9 : don't check, already covered by 18
10 : don't check, already covered by 20
11 : check
12 : check
13 : check
14 : check
15 : check
16 : check
17 : check
18 : check
19 : check
20 : check

The second observation is that we don't every to try each number. For example, we know that the number has to be a multiple of 2, so we only need to try every even number. We know that the number also has to be a multiple of 3, so we only need to try every multiple of 6 (= 2 * 3).

You might be tempted to say: we also know the number has to be a multiple of 4, so we only need to try every multiple of 24 (= 2 * 3 * 4). However this is obviously wrong since 12 is divisible by 2, 3, and 4. The reason for this that 4 is already a multiple of 2.

If we factor each of the numbers 1 thru 20 into their prime factors as shown below we can see that we only need to check multiples of 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560.

1 : 1
2 : 2
3 : 3
4 : 2 2
5 : 5
6 : 2 3
7 : 7
8 : 2 2 2
9 : 3 3
10 : 2 5
11 : 11
12 : 2 2 3
13 : 13
14 : 2 7
15 : 3 5
16 : 2 2 2 2
17 : 17
18 : 2 3 3
19 : 19
20 : 2 2 5

I wrote an Erlang program which uses a "brute force" approach to find the solution using the above two optimizations.

I put "brute force" between quotes because the Erlang program finds the solution on the very first iteration; I had not realized that I had already solved the problem on paper and that the answer is 232792560.

%% Project Euler, problem 5
%%
%% 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
%%
%% What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

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

-export([solve/0]).

-define(TRY_INTERVAL, 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19).
-define(DIVISORS, [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]).

isDivisibleBy(_N, []) ->
    true;

isDivisibleBy(N, [H|T]) ->
    (N rem H == 0) and isDivisibleBy(N,T).

solve() ->
    solve(?TRY_INTERVAL).

solve(Try) ->
    case isDivisibleBy(Try, ?DIVISORS) of
        true -> Try;
        false -> solve(Try + ?TRY_INTERVAL)
    end.

Erlang solution for Euler problem 4

In Euler problem number 4 we have to find the largest palindrome number which is the product of two 3-digit numbers.

Once again, since I am only doing this to learn Erlang, I simply went for the brute force approach: try all combinations of 3-digit numbers, multiply them, check whether the product is a palindrome, and remember the biggest one.

While working on this problem, I did learn a couple of interesting things about the if statement in Erlang which seem weird coming from a more traditional language like C++. In Erlang every if statement must have an else clause, even if you don't really need one. Also, you cannot call a function in the condition. Damien Katz's excellent blog on "What sucks about Erlang" discusses these restrictions as well as some other restrictions.

Project Euler has a one-minute rule which says that the run time of a solution must be less than one minute on a modestly powered computer. Although the run time of this solution was obviously less than one minute, I wondered how I would measure it in Erlang. It turns out that this is trivial: just call timer:tc(module, function, arguments). This is described in detail in this article on the trapexit website.

(erlide@cayle-spandons-computer.local)2> timer:tc(euler4, solve, []).
{444625,906609}

Here is my Erlang solution for Euler problem number 4:

%% Author: cayle.spandon
%% Created: Jan 9, 2009
%% Description: Project Euler, problem 4
%%
%% A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers 
%% is 9009 = 91 × 99.
%% 
%% Find the largest palindrome made from the product of two 3-digit numbers.
%%
%% Use the dumb as a brick brute force approach: try all combinations of two 3-digit numbers, multiply them, check if 
%% the product is a palindrome, and remember the biggest one.
%%
%% I'm sure that the project Euler will have something much more clever, but -hey- I am trying to learn Erlang, not 
%% trying to become a math genius.

-module(euler4).

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

reverse(N) ->
    reverse(N, 0).

reverse(N, Reversed) ->
    if 
        N == 0 -> Reversed; 
        true -> 
            NLastDigit = N rem 10,
            reverse(N div 10, Reversed * 10 + NLastDigit)
    end.

isPalindrome(N) ->
    N == reverse(N).

solve() ->
    solve(100, 100, 0).

solve(N1, N2, BestSoFar) ->
    Product = N1 * N2,
    case (Product > BestSoFar) and isPalindrome(Product) of
        true -> NewBestSoFar = Product;
        false -> NewBestSoFar = BestSoFar
    end,
    if
        N1 < 999 -> solve(N1+1, N2, NewBestSoFar);
        N1 == 999 ->
            if
                N2 < 999 -> solve(100, N2+1, NewBestSoFar);
                N2 == 999 -> NewBestSoFar 
            end
    end.

Erlang solution to Euler problem 3

Here is what I cooked up as a solution for project Euler problem number 3:

%% Author: cayle.spandon
%% Created: Jan 8, 2009
%% Description: Project Euler, problem 3
%%
%% The prime factors of 13195 are 5, 7, 13 and 29.
%%
%% What is the largest prime factor of the number 600851475143 ?

-module(euler3).

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

solve() ->
   solve(600851475143).

solve(N) ->
   solve(N, 2).

solve(N, Try) ->
   if
       Try > N div 2 ->
           N;
       true->
           if
               N rem Try == 0 ->
                   solve(N div Try, Try);
               true ->
                   solve(N, Try+1)
           end
   end.  

Erlang solution to Euler problem 2

Once you have solved a problem and entered the correct answer on the project Euler website it gives you access to a PDF file and a discussion thread which discusses possible solutions to that problem. I won't give away any hints, but it turns out that there is a much better way to solve problem 1 than the brute force approach which my program used. It looks like I might not only learn Erlang but also a thing or two about math...

Since it didn't take much time to come up with a solution for problem 1, I decided to do problem 2 today as well. Here is what I came up with:

-module(euler2).

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

solve() ->
solve(4000000).

solve(Max) ->
solve(Max, 1, 1, 0).

solve(Max, Current, Prev, Total) ->
if
    Current > Max ->
        Total;
    Current rem 2 == 0 ->
        solve(Max, Current+Prev, Current, Total+Current);
    true ->
        solve(Max, Current+Prev, Current, Total)
end.

Erlang solution to Euler problem 1

I've decided to get serious about learning Erlang by solving one project Euler problem a day. Here's what I came up with for problem 1.

-module(euler1).

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

solve() ->
   solve(999).

solve(N) when is_integer(N) ->
   if
       N == 0 ->
           0;
       N rem 3 == 0 ->
           N + solve(N-1);
       N rem 5 == 0 ->
           N + solve(N-1);
       true ->
           solve(N-1)
   end.