FSharp.it

There was some buzz concerning my last post on Project Euler Problem 5, since the solution presented implemented a naive brute-force algorithm and its performance was very poor.

In my mind it was only meant to be an introductory article devoted to presenting a first solution to a common problem, the least common multiple (LCM) of a set of numbers, and I planned to write a second post (the one you are reading now) to show how a “smart” algorithm could lead to outstanding performance.

Let’s read the text of the exercise another time:

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?

As we already explained, the exercise just asks us to find the least common multiple of all numbers from 1 to 20, and we can compute it by using the greatest common divisor of these numbers.

In fact, we have that:

lcm (a,b) = a * b / gcd (a,b)

In order to compute the LCM of the numbers from 1 to 20, we start computing the LCM of the first two numbers (1 and 2) and then we go on computing the LCM of the result and the third element of the sequence. We go on this way until all elements have been included in the computation.

The application of the same function to all elements of a sequence while keeping an “accumulator” is called folding, and it is a common practice in functional programming.

Let’s look at the code:

#light
open Microsoft.FSharp.Math.BigInt

// Greater Common Divisor
let rec gcd a b =
 match b with
 | b when b = 0I -> a
 | b -> gcd b (a % b)

// Least Common Multiple
let lcm a b = a * b / (gcd a b)

let answer = Seq.fold1 lcm [1I .. 20I]

At line 11 we defined the least common multiple as explained above, while at line 5 we have the implementation of the Euclidean algorithm for the Greatest Common Divisor.

Then we simply fold the lcm function on the sequence [1 .. 20] and we get the output.

Do you remember how much time our “optimized” algorithm in the last article takes to perform the same calculation? 25 seconds.

The solution presented here only needs 15 milliseconds!

The exercise we are going to face today is ranked as one of the easiest of Project Euler’s, so I don’t think you will have any problem in solving it.

However, it allows me to discuss a little bit on algorithm optimization and how to refine a working solution to obtain a better one.

The text of the exercise says:

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?

Some programming languages (for instance Haskell) provide a native function for evaluating the least common multiple (LCM) of two numbers, i.e. the smallest positive integer that is multiple of both numbers.

In F# we don’t have this function, hence we have to write our own code to perform this calculation, and we need it to be able to find the LCM of a set of numbers and not only two.

Let’s see the implementation of my algorithm:

#light
open System

let nums = 1 |> Seq.unfold (fun i -> Some (i, i + 1))

let divisibleByList list n =
    Seq.for_all (fun x -> n % x = 0) list

let answer = nums |> Seq.first (fun i -> if divisibleByList [1 .. 20] i then Some (i) else None)

My solution will simply take the integers starting from 1 and check if they are evenly divisible by all numbers from 1 to 20.

We don’t know when to stop, so at line 4 we have to create an infinite list of integers.
To do so, we use the unfold function, which allows us to create a lazy list by passing another function to be repeatedly evaluated to provide the elements of the list.

In our case we start from 1 and for each iteration we add one to the previous value, without an upper limit.

At line 6 we have the definition of the divisibleByList function, which takes a list of numbers and an integer n and checks if n is evenly divisible by all the elements of the given list.

This is done by using Seq.for_all, which tests if all the elements of the sequence satisfy the given predicate.

We have now everything we need to find our solution.
Let’s just feed the divisibleByList function with the elements of the infinite list of integers and stop when we find the first that satisfy our conditions, thanks to Seq.first.

The solution is complete, but it is not very fast, since it takes about 8 minutes to run in my computer.

We can improve this time by using some very simple math.
First of all, we are sure that the number we are looking for will be a multiple of 2, so we can skip all odd numbers, by changing line 4 with:

let nums = 2 |> Seq.unfold (fun i -> Some (i, i + 2))

With this simple change the execution time drops to 4 minutes, as the amount of integers to check is is actually halved.

I want to go a little further and instead of checking all even numbers we can just test the multiples of 20.
To do so, we change again line 4 with this new one:

let nums = 20 |> Seq.unfold (fun i -> Some (i, i + 20))

Now I can be proud of myself as the execution time is reduced to 25 seconds, twenty times less than the original solution!

Obviously this is not the only solution and there are smarter approaches, maybe we can see them in a future post.

This time we are gonna “cheat“.

As in Problem 20 we have to sum the digits of a number, so we can just copy and paste the whole code and edit a single line to have a working solution.

The problem says:

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

The only difference between this exercise and the last one is the number to evaluate.

However, as for the factorial, F# already provides us with a native function for the powers of a numbers, so the final code will be:

#light
open Microsoft.FSharp.Math.BigInt

let rec digits n =
    match n with
    | n when n < 10I -> n
    | n ->
        let x, y = divmod n 10I
        y + digits x

let answer = digits (pow 2I 1000I)

If you compare this exercise with the last one, you can see that we actually changed one line, i.e. line 11.

Do you really want me to explain this code?

Project Euler’s Problem 20 was trickier than I expected.

I’m quite sure that there is a smart solution, but there is also a “dumb” one and this is the one I’m going to present you.

The problem says:

n! means n × (n − 1) × … × 3 × 2 × 1

Find the sum of the digits in the number 100!

Evaluating the factorial is straightforward in any functional language, but it is even easier in F# since the language already provides us with the factorial function.

As usual, let’s show the code and then analyze it:

#light
open Microsoft.FSharp.Math.BigInt

let rec digits n =
    match n with
    | n when n < 10I -> n
    | n ->
        let x, y = divmod n 10I
        y + digits x

let answer = digits (factorial 100I)

The open directive at line 2 permits the use of the BigInt namespace, which is needed when working with very large numbers.

Then we have the code to sum the digits of a number, which is easily implemented with pattern matching.

The algorithm is based on the modulus operator, since taking the last digit of a number is equivalent to taking the remainder of the number itself divided by 10 (in a base 10 system).

Hence, we take the last digit and recursively apply the same function to the rest of the number, until there is only one digit left, i.e. the number is less than 10.

This operation is done by the divmod function, which returns the integer quotient and the remainder as a couple (x, y).

You may have noticed that there is a capital “I” after each number. That letter stands for Big Integer and is used to distinguish them from normal integers.

It’s done, we just have to apply the digits function to the output of factorial 100I.

Why did I call this solution “dumb“?

Because I had to compute 100! (which is a number with 158 digits) and then sum its digits, but this solution is not feasible if the number becomes much larger.

I think that there should be some mathematical trick to do the same job, but I don’t know it.

Does anybody have a different approach to suggest?

Today’s exercise is Project Euler Problem 9, that says:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Therefore this time we have to find a triplet (a, b, c), but a brute-force approach would require a billion combinations, since the three numbers can range from 1 to 1000.

However, we can reduce the number of tests exploiting a little algebra.

First of all, c = 1000 – a – b, so only two variables are in play, leading us to a million choices.

Then we go down to half a million, thanks to the constraint that a < b.

According to these premises, here is the F# code:

#light
let sq x = x * x

let ab =
    { for a in 1 .. 1000
      for b in a .. 1000 -> a,b } |> Seq.filter (fun (a,b) -> sq a + sq b = sq (1000 - a - b) ) |> Seq.hd

let answer =
    let a = fst ab
    let b = snd ab
    let c = 1000 - a - b
    a * b * c

At line 5 we enumerate all items of a collection created with list comprehension, i.e. the numbers between 1 and 1000.

Inside this loop we have another loop, but in this case we are interested in all numbers bigger than the current item of the outer collection, i.e. all numbers between a and 1000.

Then, we filter all couples (a, b) keeping only those for which we have: a² + b² = (1000 – a – b)².

According to the text of the exercise, there exists exactly one Pythagorean triplet that satisfies the equation a + b + c = 1000, so we can apply the Seq.hd (head) function to take the first (and only) element of the generated sequence.

At lines 9, 10 and 11 we evaluate a, b and c and finally we multiply them to get the answer.

The exercises proposed by Project Euler are ordered by difficulty, and the one I’ll discuss today is ranked sixth.

However, I think it is one of the easiest to solve, since it doesn’t require any trick and the solution is already written in its text:

The sum of the squares of the first ten natural numbers is,
1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)² = 55² = 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.

We just have to evaluate two formulas and then perform a subtraction, so let’s go directly to the F# code:

#light
let numbers = [1 .. 100]

let diff =
   (numbers |> Seq.fold (+) 0 |> (fun x -> x*x)) -
   (numbers |> Seq.sumByInt (fun x -> x*x))

You should already know the pipeline operator, which is massively used in F#.

Seq.fold is used to apply a function (in our case the sum operator) to all the elements of a collection (i.e. the list of numbers) starting from a base value that we set equal to zero.

Then we pass the result to a function that takes a number and returns its square, actually giving us the square of the sum of the first 100 numbers.

In the next line of the diff function we evaluate the sum of the squares of the first 100 numbers.

It is done thanks to the Seq.sumByInt function that returns the sum of the results generated by applying the given function (i.e. the square function) to each element of the collection.

That’s it, no tricks and no special mathematical knowledge required, I told you!

In the last article I presented a naive solution for the first Project Euler problem, that asks us to “find the sum of all the multiples of 3 and 5 below 1000“.

There are many different solutions for the same problem and today I want to show an alternative approach, which is based on a mathematical formula for an arithmetic series.

In our first solution we examined all numbers between 1 and 999 and only kept the multiples of 3 and 5, skipping all the others.

Instead of doing this, we just need to generate the multiples of 3 and 5 and sum them, subtracting the multiples of 15 because they will be included twice.

Remembering that the sum of the first n integer numbers is equal to n * (n+1) / 2, we need to adapt this formula to sum the multiples of a given number, i.e. 3, 5 and 15.

Let’s call n the the result of the integer division between the maximum value (in our case 999) and step, where step is 3, 5 or 15.

According to this naming, the sum of multiples will be step * n * (n + 1) / 2, and this formula is very easy to translate in F#:

#light
let sum_mult max step =
  let n = max / step
  step*n*(n + 1)/2

let max = 999
let sum = sum_mult max 3 + sum_mult max 5 - sum_mult max 15
print_any sum

At line 2 we define the sum_mult function, which takes two integer arguments this time: max and step.

The next line shows how to define a local identifier called n, whose scope is limited to the sum_mult function.

The rest of the code is straightforward, we apply the formula to sum the multiples of 3 and 5 and subtract those of 15.

Comparing the complexity of this solution with the previous one we can easily see that we moved from O(n), i.e. going through all the elements of the array, to O(1).

In fact, with this approach the number of evaluations is always fixed to 3, regardless of the maximum number to take into account.

Next time we’ll face a new problem, I look forward to receiving your comments.

I’m going through two parallel roads to learn F#: I read the “Foundations of F#” book written by Robert Pickering for the theoretical aspects and then I practice writing some code challenging myself with the problems proposed by Project Euler.

There are currently 177 mathematical exercises that can be ordered by difficulty, so I think that as soon as I solved them I’ll master all aspects of F#.

Maybe my solutions are not the best at all, but I’ll show them to you and I’ll try to use them to explain F# programming while I’m still learning it.

Feel free to ask questions, comment or propose alternative solutions, I’ll be glad to compare mine with yours.

So, let’s start with the first exercise, which says:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This is a very good introductory exercise and can be used to understand the power of the functional paradigm.

Here is the first version of my code, the explanation will be just below:

#light
let rec sum_mul xs =
  match xs with
  | []    -> 0
  | y::ys when y % 3 = 0 || y % 5 = 0 -> y + sum_mul ys
  | y::ys -> sum_mul ys

let sum = sum_mul [1 .. 999]
print_any sum

The #light clause at line 1 allows us to write code with a simpler syntax, without all the symbols and keywords, such as begin and end.

At line 2 we have the definition of a recursive function called sum_mul that accepts an argument called xs.

To define functions and literals (we don’t call them variable, since their value never changes) you need to use the let keyword.

Then, in lines 3-6 we have an example of pattern matching, that is a common practice in functional programming similar to the switch statement of the imperative paradigm.

It compares xs with some patterns, which are written one per line, with a | (pipe) in front of each of them.
The first case is matched when xs is an empty list, and in that case sum_mul simply returns 0.

In the other cases xs is matched against a list, with the first element (the head of the list) being called y and the rest of the list (the tail) called ys.

If y is evenly divided by 3 or 5 (using the modulus operator: %) we add the number to our result and then recursively apply the same function to the tail.
Otherwise we just skip the head and call sum_mul on the tail.

At line 8 we actually call the sum_mul function passing a list as the argument. This list is composed by all integers between 1 and 999.

Line 9 is just used to print the output to screen.

If you want to run this code you can use Visual Studio with the F# plugin installed or simply run the F# interpreter, which is a command line tool called fsi.exe and is installed with the F# package.

I hope the explanation was clear and you started to appreciate the power of functional programming.
In the next article I’ll show you an alternative (and much faster) solution to the same problem.