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!

Video Version

If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!

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 it is not divisible, skip to the next number
          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

I'm writing a book about graphic design and how it relates to software development! If you're interested, sign up here for updates.

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

https://www.youtube.com/channel/UCqxQspCPTcE_wH0KBE5J-aw

https://music.apple.com/us/artist/modulo/1499420471

Support

If you like this article and want to see more, the best way to do that is to subscribe/follow me on here! If you are feeling gracious, you can buy me a coffee!