## Project who?

Project Euler is probably the largest (270 problems as of December 2009) and best collection of brainteasers specifically designed for programmers. Unlike other puzzles they are not only fun and challenging, but also help you discover and develop new patterns and programming techniques. I'm a big fan of similar computational mind-benders and use them both in job interviews to see how a candidate approaches a real problem and as a way to balance the boring work that's frequently necessary for even the most interesting projects.I've been solving 1-2 problems every day and after completing number 25 today I got a nice message:

"Bravo, dragozov! Now that you have solved 25 problems you have achieved what 80.04% of members have failed to do and have advanced to level 1. Good luck as you continue."

So I thought I'd describe my experience, especially considering that I'm using Erlang, a language that I'm currently trying to master and which could use a little more sample code and demos online.

## Why Erlang?

I'm working on a small side project and one of the decisions I made was to focus on learning new things and exploring technologies and problems that I find interesting, but are not useful or relevant to my day job. So I'm developing everything as a combination of Erlang and Python.Of course I have more pragmatic reasons. Erlang's unique features make lots of sense for some parts of my app and the two languages complement each other quite well. I also wanted to experiment a little more with functional programming and I find the mental shift required to code in Erlang quite enjoyable. I guess the recent hype around the language played its role too.

Anyway I've been studying Erlang and OTP (the open source platform behind it) and use any chance to apply my new skills, so Project Euler was too good of an opportunity to miss.

## The Idea

In this and the follow-up articles I'm showing how to use Erlang to solve computational problems. As I advance from the simpler questions to the harder ones, I'll try to also move from the language's basics to more advanced topics.However this is not an introduction and I won't be explaining the syntax. There are a few good online tutorials and an excellent book, so you might want to check them first.

On the other hand I'll point out Erlang specific features and techniques and discuss their usage. I also keep the solutions as self-contained as possible, so in some cases there might be code implementing functionality that is already available in the standard libraries or functions copied between the modules.

I've tried to find the best solutions I could think of and optimize the code as much as possible, but I haven't searched the Internet or checked the forums, so there might be better/faster algorithms. There is rarely a single correct way of doing things in programming and this is not an exception.

I'll keep all solution sources in a Google Code project called Eulerl. The license is BSD, if you care, so you are free to use them for anything you like.

## Level 1 (first 25 problems)

SumM = 1*M + 2*M + ...+ K*M = M*(1+2+...K)=M*(K*(K+1)/2)

We add the sums of the multiples of 3 and 5 and subtract the sum of the multiples of 15 as they were added twice.

Not much to be seen here, just 2 simple function declarations and the use of the div operator for integer division.

Although it's still a very simple problem, things get a little more interesting.

First we have an example of a tail-recursion, the most common (and efficient) way of implementing iterations in Erlang. I use the function's arguments, including an accumulator (a very common pattern for keeping track of the result) to keep the recursion's state between subsequent calls. At each step of the iteration the function receives the complete information and returns the whole result.

The code also demonstrates some basic usage of pattern matching and guard expressions. Although they don't make a big difference here, they can make the code for an algorithm shorter and more readable (my personal opinion, of course).

Similarly to problem 3 I use tail-recursion and pattern matching to code the solution. Note the rem operator, which is Erlang's operator for modulo (the remainder of the division of one number by another).

So to solve the problem I iterate backwards starting with 999 and ending with 100, generate all 6 and 5 digit palindromes and return the first that is a product of two 3 digit numbers.

On the Erlang side the most interesting is the use of functions as first-class elements of the language. You can see them passed as arguments to other functions and assigned to local variables.

Also note the syntax for declaring anonymous (fun) functions and how they have access to the enclosing context (the arguments of the factor/3 function for example). One of the quirks of an anonymous function in Erlang is that it can't call itself directly, so to implement recursion I pass the function as one of its own arguments (Funself is my naming convention, not a rule).

The palindrom_iterator function is interesting for a few reasons.

First it shows a common approach in functional programming. It defines some generic functionality and lets you change the behavior later by accepting a function as one of its arguments. In this case palindrom_iterator iterates through the palindromes and applies the function to each one. Then based on the result it either returns it or continues with the next palindrome.

Second it demonstrates how pattern matching can simplify complex logic. In this case the function iterates through all palindromes bellow a given size (although its not strictly a requirement for the solution). For example if we start with length 6, then we'll iterate through lengths 5, 4, 3 and 2. As it uses numbers half the length to generate the palindromes, there are two cases when it reaches the lowest number of a given length. If it was generating even length numbers, we need to run the same iteration but for odd length palindromes, else we need to reduce the length of the "template" numbers and switch to even palindromes. This is all encoded in only 4 lines at the 2nd and 3rd patterns of the function's declaration.

^{3}and 18 = 2*(3

^{2})) with maximum powers 3 and 2 respectively. So the solution would be (2

^{3})*(3

^{2})=72.

There are a few new concepts introduced in the Erlang code:

- The use of a look-up table (in the max_count functions) implemented using the ets module, an efficient library for storage and access of data in a table form.

- List comprehensions (in the solution/1 method), Erlang's syntax for "functional" creation of lists.

- The syntax for splitting a list into a "head" element and a "tail" sublist or constructing a list in a similar fashion ([H|T] = List and List = [H|T]).

- The lists module, one of the most used standard libraries.

(a+b+c +c...+y+z)

^{2}= a

^{2}+b

^{2}+c

^{2}...+y

^{2}+ z

^{2}+ 2*a*b + 2*a*c...+2*a*y+2*a*z + 2*b*c + ...+ 2*b*z + ...2*y*z

so:

(a+b+c+...+y+z)

^{2}- (a

^{2}+ b

^{2}+ c

^{2}+...+ y

^{2}+ z

^{2}) = 2*(a*(b+c+...+y+z) + b*(c+...+y+z) + ...+y*z)

The actual implementation is another example of a tail-recursive function, where the state of the computation is kept in the function's arguments.

(1) A

^{2}+ B

^{2}= C

^{2}

(2) A + B + C = N

If we postulate that A is the smallest and C the biggest number, we can extract two additional constraints:

(3) A < N/3

(4) B < N/2

I run an iteration through all possible A, for each run another nested iteration through all possible B and check if the resulting triplet {A, B, C} meets all the conditions and constraints (1,2,3 and 4).

The code also demonstrates the use of tuples to return and unpack multiples values as a result of a function.

The code introduces the array module, providing functions for working with arrays in Erlang (0 based unlike most other data structures). It's also an example of extensive use of anonymous (lambda) functions to simplify the implementation of complex logic.

(1) Tn = n*(n+1)/2

n and n-1 can be written as products of prime factors:

(2) n = 2

^{p2}*3

^{p3}...*N

^{pN}

(3) n+1 = 2

^{q2}*3

^{q3}...*M

^{pM}

so Tn:

(4) Tn = 2

^{(p2 + q2 - 1)}*3

^{(p3 + q3)}*...*K

^{(pK+qK)}, K is the max of M and N and pi,qi >= 0

If the prime factors of x are:

(5) x = 2

^{s2}*3

^{s3}*...*L

^{sL}

then all possible divisors of x have the form:

(6) D = 2

^{t2}*3

^{t3}*...*L

^{tL}, where 0 <= ti <= si

So the total number of unique divisors of x is:

(7) Divisors(x) = (s2 + 1)*(s3+1)*...*(sL+1), adding 1 for the case where ti = 0 (see 6 above)

From 4 and 7:

(8) Divisors(Tn) = (p2 + q2)*(p3+q3+1)*...*(pk+qK+1)

First I implement a method that returns all the prime factors and their powers. Then I iterate through the triangular numbers and calculate expression 8 for each until I finds the first that meets the problem's condition.

The code is another example of a recursive function, with the optimization of reusing (through the function's arguments) the calculated factors and their powers for each number in two consecutive calls, as the (n+1) in one triangular number is the n in the next.

^{0}), repeatedly calling the function with the result of its previous call. Nothing much else to be seen here.

Every node is represented by a tuple of four items. First the value of the node itself, then the tuples of the left and right children (or empty tuples if it's the bottom row) and then the "weight" of the node - the sum of the its value with the maximum weight of its children (as a matter of fact we only need to keep the weights). Building the tree from the bottom up gives the solution as the weight of its root.

(1) DivisorsSum(x) = (p2

^{0}+p2

^{1}+...+p2

^{k2})*(p3

^{0}+p3

^{1}+...+p3

^{k3})*...(pN

^{0}+pN

^{1}+...+pN

^{kN}), where k2,k3, ...kN are the powers of each prime factor of x

Using this we can iterate through all numbers and check if they are amicable and meet the other conditions of the problem, then sum them into the result.

However the code introduces some important libraries and concepts:

- Working with files is usually done using the file module (and a few others usually prefixed with file_).

- The binary syntax and the pattern matching are a very powerful combination frequently used as a replacement for the standard (and somewhat limited) representation of strings as lists of integers. They make it really easy to parse and construct streams of bytes, while keeping the code short and readable. A personal favorite of mine.

I could have probably used standard libraries for a few of the functions, but chose to implement them myself:

- The qsort function demonstrates a very cool (but not optimal) one-line implementation of the QSort algorithm using list comprehensions, guard expressions and recursion.

- The a2i function demonstrates the syntax for retrieving the integer value of a character by prefixing it with a '$'.

- The split function demonstrates the binary syntax as discussed above.

(1) SumNA(Max) = Sum(Max) - SumA(Max) = Max*(Max + 1) /2 - SumA(Max)

If we know all abundant numbers in the range their sum can be calculated like this:

(2) SumA(Max) = (2*A1 + 2*A2 + ...+ 2*AN + (A1 + A2) + (A1 + A3) + ...+ (A1+AN) + (A2+A3) +...), where A1,...,AN are all abundant numbers bellow Max

So my solution is to iterate through all numbers in the range, check if they are abundant and update their sum according to formula 2 above. Then the solution is computed using formula 1.

The code is a combination of previous techniques, so nothing much to be explained.

## Conclusion of Level 1

This was the first post about my experience as I move through the problems. It's a demonstration of the sequential style of programming in Erlang. In the future I intend to focus on the parallel and distributed concepts of the language, which is what makes it so different. I hope that the problems will get a little harder and less repetitive so that I'll be also able to introduce and experiment a little more with the OTP modules.## Links

http://projecteuler.net/ - the home page of Project Euler.http://erlang.org/ - the home page of the language.

http://code.google.com/p/eulerl/ - my project at Google Code, where I keep all the sources.