Functional Practice: Euler Problem #5 in F# - Brute Force Version

In continuing my exploration of F#, it's time to look at Euler Problem #5. I found a brute force approach to this as well as a more mathematical approach. Both are worth looking at.

Here's 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 positive number that is evenly divisible by all of the numbers from 1 to 20?

As with the prior problems, we'll start by replicating the sample case and then apply it to the target case.

[Update: Collected articles for the first 10 Euler Problems in F# are available here: Jeremy Explores Functional Programming.]

Evenly Divisible
I figured that it would be good to start with a test to see if a number is evenly divisible by all of the numbers in our range (1 to 10). We can check if something is evenly divisible by using the modulus operator (%). This gives us the remainder of division. If the result is "0", then we know it's evenly divisible.

To get this to work with a range of numbers, I ended up with the following function (showing the code from a script file and the output from the F# Interactive window):

This starts with our range (1 to 10), and then calls a function against each value (this is one thing "forall" does). The internal function will return true or false depending on whether the number is evenly divisible by the value from our range.

"forall" will return true or false depending on whether all of the results are true. This means that we'll be able to tell whether something is evenly divisible by all numbers in our range.

Here are a couple of sample runs:

We can see that "30" is not evenly divisible by all the numbers from 1 to 10, but "2520" is evenly divisible. (And that's what our sample says it should be.)

Brute Force Attack
Since we're looking for the smallest number that is evenly divisible by everything in our range, I figured it would be easiest to just start with 1 and keep incrementing the number until we find something that passes our "divisibleBy" function.

For this, I just built up a sequence. Let's take this one step at a time:

This will initialize our sequence with a series of values. Each item in the sequence is actually a tuple of 2 values. The first is the number itself, and the second is the true/false result from using our "divisibleBy" function.

If we look at the output, we see that the sequence starts with 0, which is evenly divisible by everything. So we'll want to eliminate this value:

By skipping the first value, we eliminate the 0. Technically, we could probably eliminate the values up to the maximum of our range as well, but we won't worry about that.

Now that we have our sequence, I want to find the first "true" value. This will be the smallest number that is divisible by everything in our range:

Since I want to skip over everything until I hit a "true", I use the "skipWhile" function. Inside here, we look at our tuple (x,b) -- where x is our number and b is true/false -- and keep skipping while "not b". This means that we will skip all of the false values and start at the first "true".

And we can see by the output that this is exactly what we get. Our first value is "2520". And this matches the expected result of our sample.

Now we can pick out the element that we want:

First we'll use "head" to get just the first item of our sequence. Then we'll use "fst" to pick out the first value of the tuple:

And this gives us the value that we want: 2520.

Putting Things Together
Now that we have the pieces that we need, let's put them together into a single function:

The "euler4a" function takes a range of values as a parameter. We can see that "divisibleBy" is now a local function, and then we have the sequence.

We can run this against our sample range:

And we see that we get the expected output of 2520 (just like we saw above).

Now we can try this with our target range: 1 to 20:

This gives us a result of 232,792,560. And we can look online to see that this is the correct answer.

Performance
I'm happy about getting a correct result. But I'm not too happy about the performance. With the timing turned on, we can see that it took over a minute to get the result back. And that's because we're doing a lot of calculations. We're checking over 200 million numbers against our range of 20 values. That means we're running over 4 billion calculations.

This is what computers are good at -- lots of calculations very quickly -- but we can make this better.

A Better Path
After getting the brute force method to work, I started thinking about a better way to get this result. And that took me back to 6th grade math and calculating prime factors.

I took a stab at this, ran into a bit of a stumbling block, and got a ton of help from the F# community. And that's what we'll look at next time.

Update: Read about that here: Euler Problem #5 - Faster with Math & Help from the Community.

Until then...

Happy Coding!