On to the next Project Euler problem (after a bit of a hiatus)...

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 divisibleby all of the numbers from 1 to 20?

In common with many of the other Euler problems, there's a brute-force way to solve this, and a clean algorithmic way. And in common with my other Euler posts so far, I'll start with the brute-force way ;-)

This problem can be tackled head-on with the following approach: Start
from *n*=1 and increment in a loop. Test each value of *n* by attempting
to divide it by all numbers *m* from 1 to 20. The first number to pass
the test (i.e. *n* mod *m* is 0 for all values of *m*) is the answer.

```
private static long BruteForceSolver()
{
long result;
for (result = 1; !Check(result); ++result)
;
return result;
}
private static bool Check(long result)
{
for (int i = 1; i <= 20; ++i)
{
if (result % i != 0)
return false;
}
return true;
}
```

This works, but it takes >12 seconds to execute on my PC, so it's not what you'd call efficient (though it is well within the Euler execution time guidelines).

Some speed gains can be achieved by exploiting the information provided in the question itself. We are told that 2520 is the lowest number evenly divisible by all numbers from 1 to 10. Since the problem space (1 to 20) includes all these numbers, the answer must also be evenly divisible by 2520. This allows much bigger increments each loop - rather than incrementing by 1, why not increment by 2520? And since the answer must be greater than or equal to 2520, why not start the loop there instead of 1? Finally, since we already know that 1 to 10 divide evenly into 2520, each inner loop only needs to check numbers 11 to 20.

That should speed things up a bit:

```
private long BruteForceSolver()
{
long result;
for (result = 2520; !Check(result); result += 2520)
;
return result;
}
private bool Check(long result)
{
for (int i = 11; i <= 20; ++i)
{
if (result % i != 0)
return false;
}
return true;
}
```

And indeed, on my machine this is now down to 150ms or so. It's still not a very nice way to tackle the problem, though.

Thinking about it from a different angle yields an altogether smarter approach. Imagine we are looking for the lowest number evenly divisible by the numbers 1 to 2.

```
[1, 2]
```

Well that's easy; since there are only two numbers we just find the
lowest common multiple (LCM), which in this case is 2 (since 2 % 2 == 0,
and 2 % 1 == 0). If we call this sequence s_{1}, we can say that
\(LCM(s_1)=2\).

OK, now imagine we are solving the same problem for s_{2}, which contains
the numbers 1 to 3.

```
[1, 2, 3]
```

You'll notice that s_{2} contains s_{1} in its entirety. \(LCM(s_2)\) must
therefore be a multiple of \(LCM(s_1)\), so we can rewrite s_{2} as
[\(LCM(s_1)\), 3], or [2, 3][2]=2\(). Now we are down
to two numbers again, so we can calculate the LCM of 2 and 3, which is
6, so $LCM(s_2)=6\).

OK, now we solve the problem for the first 4 numbers (s_{3}).

```
[1, 2, 3, 4]
```

This sequence contains s_{2}, therefore \(LCM(s_3)\) is a multiple of
\(LCM(s_2)\). We can rewrite s_{3} as [\(LCM(s_2)\), 4], or [6, 4]. Thus,
\(LCM(s_3)=12\).

This can be repeated as many times as necessary. Generally, we have
s_{n} = [\(LCM(s_{n-1})\), *n*+1] where *n* > 0.

This looks recursive, but a better way to think of it is as an excellent
example of a fold. A fold is one of the fundamental tools of functional
programming. In fact, it is perhaps the most fundamental, since map,
filter etc can be implemented as right folds^{1}.

I won't inflict my pitiful Photoshop skills on anyone by trying to graphically represent a fold - try looking at this Wikipedia article if you want to try and visualise it.

Broadly, the behaviour of a fold is to apply a combining function to
elements in a list (or other data structure) and accumulate the results.
That's exactly what we want here - our combining function is LCM, and
our accumulating value is the LCM of the whole list. Effectively, for
list s_{3} above, we have

Note how the result of the innermost LCM (applied to values 1 and 2) becomes a parameter to the next LCM, which in turn becomes a parameter to the outermost LCM which returns the result we want.

By using a fold, we can generalise. In Haskell, the whole problem is a one-liner:

```
foldl lcm 1 [1..20]
```

The 1 passed in as a parameter represents the terminating value to use when the end of the list is reached. It is common for this value to be the first element of the list, so Haskell provides a convenience function that removes the need to specify it as a parameter:

```
foldl1 lcm [1..20]
```

Not all languages and platforms provide an LCM function right out of the box, so to take this neat Haskell solution and port it to .Net, the LCM function needs to be implemented. This is easily done in terms of the greatest common divisor (GCD) like so:

.Net doesn't provide a GCD function either, so I'll implement it using Euclid's Algorithm as an extension method on long ints:

```
public static long GCD(this long a, long b)
{
while (b != 0)
{
long tmp = b;
b = a % b;
a = tmp;
}
return a;
}
```

With GCD defined, LCM can be implemented as above:

```
public static long LCM(this long a, long b)
{
return (a * b) / a.GCD(b);
}
```

With this in place, it's a simple matter to use .Net's equivalent of
fold - a method on IEnumerable<T> called Aggregate - to get the
answer^{2}:

```
return LongEnumerable.Range(1, 20)
.Aggregate(1L, (curr, next) => curr.LCM(next));
```

And indeed, the same basic pattern can be used to solve the problem in a number of languages. In F#, given implementations of LCM and GCD as above, we have:

```
List.fold_left lcm 1 [1..20]
```

And in ruby:

```
require 'rational'
(1..20).inject { |c, n| c.lcm n }
```

Given that the right algorithm makes this problem a fairly trivial expression in all these languages, it's pretty hard to identify which is the nicest. I think overall I'll give the nod to Haskell, however, for not making me implement LCM and because I find ruby's 'inject' a less intuitive function name than foldr (but that's probably because I learned the technique in Haskell in the first place and am set in my ways...)

[2]: since we know $LCM(s_1

Hi,

really good blog! I read you are familiar with Betfair API. Actually I am developing a Betfair mobile client for Windows Mobile 6 (.NETCF 2.0). When calling login method I got

`resp.errorCode == LoginErrorEnum.OK`

, but the header is null. Any solutions available?All the best, Loocie

Hi Loocie,

I haven't seen that happen before. Could you show me some sample code that exhibits the error (anonymising your login credentials, of course)?

Hi russ, thanks for your reply. Here is my login code:

The object 'resp' has an attribute called 'header' and this is null. This header object should contain a sessionToken. When using this code I can see 'Logon successfull' at betfair.com (under Account -> Security). Maybe you have an idea. This code works when using in a dektop application, but not in Windows Mobile 6.

All the best, Loocie

Awesome! That code got my solution down from 80 seconds to around 0,00125 seconds. Will have to read some more on it though, cause not sure if I understand it :P Thanks!!

Hi Torleif,

could you share your approach of getting the precise running time? Thanks!

The Haskell one-liner is a real gem. I blundered through the brute force methods first of course, and ran out of memory because I'm a haskell noob.

Then I found your elegant fold. Damn that's nice.

[...] for the implementation of the getLowestCommonMultipler() method elsewhere (see here, for example), so I won't post the implementation as it is not my own work. But identifying [...]

my java solution

[...] After doing a bit of digging, it turns out you can actually solve this problem with one line of Ruby code, quite impressive if you know what all the libraries do etc. [...]

This comment has been removed by the author.