Project Euler. Solution to Problem 1

C

Many programmers learn C or Java as their first programming language. So, let's try to solve this using C first. We will then program it using Python and Erlang and study the alternate approaches.

int main()
{
    int sum = 0;
    int i = 0;
    while (i < 1000)
    {
        if (i%3 == 0 || i%5 == 0) 
        {
            sum += i;
        }
        i++;
    }
    printf("Sum of all natural numbers below one thousand that are \
    multiples of 3 or 5 is: %d\n", sum);

    return 0;
}

Python

The same program is rewritten in Python as:

total = 0
for i in range(1000):
    if i%3 == 0 or i%5 == 0:
        total += i
print "Sum of all natural numbers below one thousand that are multiples \
        of 3 or 5 is: ", total

Both the above solutions are in the imperative style, wherein we express the solution by telling the language how the final answer has to be computed.

We can restate the problem in a manner fitting to the functional style, where we are concerned about what needs to be done.

"The sum of all the elements of a list which are less than thousand and also, either a multiple of 3 or 5."

Python provides some elements of functional programming via map, reduce, filter, lambda functions and list comprehensions.

Step 1: Create a list of natural numbers between 1 and 1000.

    lst = range(1000)

Step 2: Retain only the multiples of 3 or 5.

Note: Filter function in python takes two parameters, 1. a boolean function, 2. list. In this case, the boolean returns True if the given number is a multiple of 3 or 5.

def ismultiple(x):
    return x%3 == 0 or x%5==0
lst2 = filter(ismultiple, lst)

The function ismultiple can be rewritten as an anonymous function using lambda thus:

lst2 = filter(lambda x: x%3==0 or x%5==0, lst)

Step 3: Add up the multiples of 3 and 5 less than 1000

Note: reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence, from left to right, so as to reduce the sequence to a single value.

from operator import add
lst3 = reduce(add, lst2)

Putting this all together,

from operator import add
total = reduce(add, filter(lambda x: x%3==0 or x%5==0, range(1000)))

While the above solution illustrates the use of functional style, it does not feel pythonic enough. We rewrite the above program using list comprehensions, which is arguably more readable.

total = sum([x for x in range(1000) if x%3==0 or x%5==0])

Erlang

Now that we are familiar with functional approach to solving this problem, let's try to write an Erlang program to do the same.

Step 1: Generate the list of natural numbers less than 1000.

Lst = lists:seq(1,1000).

Step 2: Retain only the multiples of 3 and 5.

Lst2 = [A|| A <- lists:seq(1,999), (A rem 3 =:= 0) or (A rem 5 =:= 0)].

Step 3: Add up

Lst3 = lists:sum( [A|| A <- lists:seq(1,999), (A rem 3 =:= 0) or (A rem 5 =:= 0)]).