Jared

Posted on

# Problem 5: Smallest multiple

I am more excited to talk about this problem than any of the other problems so far. I am really happy with how it turned out and I think you will be too. Enough said, let's solve this thing!

# Problem Discussion

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

## Statement

What is the smallest positive number that is evenly divisible by all of the numbers from 1 toÂ `n`?

## Pattern Recognition

I'm sure there is a name for this phenomenon, but when you solve this problem via brute force, you will see a pattern.

The answers for the first 5 numbers is as follows: 2, 6, 12, 60, 60.

You'll notice that each number is evenly divisible by the previous number. This doesn't seem all that important immediately, but it will when we get into the double digits. For example, the smallest positive number for 1 - 20 is 232,792,560.

Let's keep that "step" in mind while we are writing our solution.

# Solution

## Steps

1. Loop over all values, starting with 2
2. Loop over each number from 1 - n
1. Check if that number is divisible, if not, go to next loop
2. If it is divisible, go to next number
3. If we reach n and all previous values are divisible, return our smallest number

# Solution

``````    function smallestMult(n) {
// setup state
let inc = 2;
let step = 2;
let smallestNum = 2;

// loop over all numbers until we find the right one.
// The sky is the limit!
while (smallestNum <= Number.MAX_SAFE_INTEGER) {
// start from our step value
for (let i = 2; i <= n; i++) {
// check if its divisibl
const divisible = smallestNum % i === 0;
if (!divisible) {
break;
}
// if it is divisible, increase our step to be our next num
if (i === inc) {
step = smallestNum;
// increase our global incrementer by 1
inc++;
}
// check if i is equal to our last digit
if (i === n) {
// if it is, congrats! We have our smallestNum
return smallestNum;
}
}
smallestNum += step;
}
}

smallestMult(20);
``````

# Performance

Before we depart, I'd like to talk a bit about performance. The brute force method of solving this problem took an average of 1100ms to evaluate the smallest multiple for 20. When I used the improved method (the step method), that runtime reduced to 7ms. That's a decrease of the runtime of more than 15000 %!

Holy cow.

# Final Thoughts

This is definitely the hardest problem I've solved so far. I could not get it to run using the brute force method, which forced me into finding another way. I'm glad I did though, it taught me a lot about math in general.

Like all things, this can be improved. If you have recommendations or improvements, throw down a comment and let me know!

As always, happy coding!

# Resources

https://www.xarg.org/puzzle/project-euler/problem-4/

https://github.com/Matt-1123/project-euler/blob/master/solutions.js

# Plugs

## Book

https://digitalnutt.substack.com/p/coming-soon?r=34slo&utm_campaign=post&utm_medium=web&utm_source=copy

## Music

I also write music! Check it out here:

https://open.spotify.com/artist/1o6CGTMPjk1C0IdK9jV2H1