Project Euler – Problem 5

This is the fourth post in my Project Euler series. The fourth problem is here.

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?

This was by far my favorite question to date. At first glance, this looks like a problem that would be easy to brute force. This however, is not the case. I slapped some crap against the wall to brute force the problem, and after my program had been running for a good half hour I decided I could rewrite it before I would get an answer.

I was tired, so I took to the internet to find an answer. Very quickly I realized that the answers I found all had one big problem. While some of them were faster than what I threw together they were still pretty slow.

First things first, we need to remember what we already know.

Note: for the remainder of this post, I got sick of specifying that we were looking for a positive number, so just remember, we only care about positive numbers. If you have a problem with that, stop being so negative.

Another Note: Assume the following notation (which is apparently common in math according to the internets: [latex]x \mid y[/latex] means x is evenly divisible by y.

Assume that I am looking for the smallest number divisible by everything from 1 to 4. I know this looks like a trivial problem, the answer is obviously 6, but bear with me.

First, we shall calculate the smallest number divisible by 1. That was hard, it’s 1.

Next, we shall calculate the smallest $latex x$ such that $latex x \mid 1 \land x \mid 2$. Our enormous amount of effort as shown it’s 2.

Next, calculate the smallest $latex x$ such that $latex x \mid 1 \land x \mid 2 \land x \mid 3$ given 2 is the smallest $latex x \mid 1 \land x \mid 2$.

We know that the answer must be a multiple of 2. If the answer is not a multiple of 2, then it would not be divisible by 2. That sentence made me feel like a genius.

Our possibilities for numbers divisible by 1, 2 and 3 is the sequence 2, 4, 6, 8…

We know the answer is not 2 because [latex]2 < 3[/latex], likewise [latex]4 \nmid 3[/latex]. Finally $latex 6 \mid 3$

Now that we’ve finally made it this far, we calculated the smallest $latex x$ such that $latex x \mid 1 \land x \mid 2 \land x \mid 3 \land x \mid 4$ given we already know that 6 is the smallest $latex x \mid 1 \land x \mid 2 \land x \mid 3$

We know that the answer must be a multiple of 6. If the answer is not a multiple of 6, then it would not be divisible by 2 and 3. Therefore, we only need to look in the sequence 6, 12, 18…

$latex 6 \nmid 4$, $latex 12 \mid 4$

Therefore, 12 is the smallest number divisible by all values from 1 to 4.

---

Now that we have that small problem figured out, we can extract an algorithm. By calculating the smallest $latex x \mid 2$ we were able to use that answer, to quickly find the smallest $latex x \mid 3$. Then we used that answer to find the smallest $latex x \mid 4$. If we hadn’t done this iteratively, and we just brute forced until we arrived at an answer, we would have had to look at all numbers 1 to 12. Instead, we were able to skip 5, 7, 8, 9, 10 and 11. This seems really small, but that’s because we were dealing with such small numbers.

If we want to find the smallest number divisible by 1 to 5, given we know $latex 12 \mid 4 \land 12 \mid 3 \land 12 \mid 2 \land 12 \mid 1$ then we know the answer must be in the set 12, 24, 36, 48, 60…

This iterative thinking allowed us to only evaluate 1, 2, 4, 6, 12, 24, 36, 48 and 60 as possibilities. So we can see how calculating the problems iteratively can save us a lot of computation over the long run.

In order to solve the posed problem, of the smallest number divisible by 1 to 20, we simply need to calculate the smallest number divisible by 1, then 1 and 2, 1 to 3, etc. And finally we will arrive at our answer iteratively.

We need a function which calculates, given x and y, what is the smallest multiple of x such that $latex x\cdot i \mid y$. For example, given 2 as x, and 3 as y, what is the smallest value of $latex 2 \cdot i$ such that $latex 2 \cdot i \mid 3$

With this function in place, we simply need to use it to iteratively calculate the smallest value divisible by 1 through 20

For anyone curious, the best answer I found online was to calculate values of $latex 2520 \cdot i$ until you find a value which is divisible by all values 1 to 20. This was when I gave up on finding a decent answer and actually solved the problem myself.