## Project Euler in F# – Problem 5

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.

## Sorting odd and even numbers in F#

An Italian Microsoft Evangelist posted today a small programming exercise on his blog, presenting the solution with **LINQ**.

The exercise says (translated from Italian by me):

Given a list of unordered numbers (for instance 1, 7, 9, 2, 3, 4, 3, 4, 2, 3, 4, 5, 2, 0, 9), create a new list with all even numbers first and then all the odd ones.

The proposed solution also goes a little further, showing not only how to split the original list into odd and even numbers, but also putting them in the correct order, thus returning "**022244413335799**".

The following is the **C# code** used:

List<int> elenco = new List<int> { 1,7,9, 2, 3, 4, 3, 4, 2, 3, 4, 5, 2, 0, 9 }; var pariEdispari = elenco.OrderBy(s => s % 2 != 0); var pariEdispariOrdinati = elenco.OrderBy(s => s % 2 != 0).ThenBy(s => s); foreach (var item in pariEdispariOrdinati) { Console.WriteLine(item); }

And now let's compare it with an **F# approach**:

#light let numbers = [ 1; 7; 9; 2; 3; 4; 3; 4; 2; 3; 4; 5; 2; 0; 9 ] let result = numbers |> List.sort Int32.compare |> List.partition (fun x -> x % 2 = 0) print_any ((fst result) @ (snd result))

As you can easily see, everything is done at **line 4**, where we apply twice the **pipeline operator** (**|>**).

This operator allows to **chain functions**, passing the output of one of them to the next one.

The same line could be written as:

List.partition (fun x -> x % 2 = 0) (List.sort Int32.compare numbers)

Line 6 is only used to print the result, but it has to take into account that the output of *List.partition* is a * tuple*, so we have to concatenate the two elements that can be retrieved with the

*fst*(first) and

*snd*(second) functions.

The **@ operator** actually concatenates the two lists.

I'm not sure that this is the best (and most elegant) solution, but I think that it is way ahead than any imperative solution, do you agree with me?