Divisible by 1 - 20

I learned quite a bit by finding the solution to this Project Euler problem:

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?

At first, I attacked the problem with the goal of writing an algorithm that could solve it. I wrote some code that went through a giant array of numbers and checked to see if each one was evenly divisible by each of the numbers 1 - 20. This taught me a lesson in writing fast applications, since my process was using brute force rather than intelligent processes to solve the problem. I happen to be working on a beautiful, vintage 2004 iBook that runs at least some Ruby applications seven times slower than Doug's machine. This means that my brute force method wasn't going to cut it.

I re-wrote my code to eliminate items from the giant array if they weren't evenly divisible by just one of the numbers from 1 - 20, thus saving my computer the trouble of figuring out the remainder of 3, 4, 5, 6... if 31 isn't divisible by 2, anyway. This step alone brought down the speed of figuring out the smallest number divisible by numbers 1 - 10 from 19 seconds to 3.2 seconds. Wow.

Still, this wasn't good enough. The calculation speed was growing exponentially with each additional divisor, and I'm a very impatient person who doesn't like to wait.

I decided that I could also reduce the number of divisors that it was checking. I wrote some code to eliminate unnecessary divisors from a divisor array. Why check to see if it's divisible by 2, 4, or 8 when you already know that it's divisible by 16? Adding in this functionality reduced the time of finding the smallest number divisible by numbers 1 - 10 down from 3.2 seconds to .8 seconds. Progress.

Still, my code was checking too many numbers. Since the final number must be divisible by 20, why not build an array that only contains multiples of 20? Using the step method, I cut down the time to find the smallest number divisible by 1 - 15 from 21 seconds down to 1.98 seconds. Even better.

During lunch, I decided to just let the program run and find the answer for the smallest number divisible by numbers 1 - 20. It took seven minutes. Who knows how long it would have taken to find the answer with my original algorithm. I didn't have the time or patience to find out.

Then, Wai Lee came up to me and said, "Hey, I think I know a way to solve the problem without any code."

This morning, I tested Wai Lee's method with a pen and paper by listing out the multiples of each number 1 - 20, eliminating duplicates, and then multiplying the list of numbers: 5*7*9*11*13*16*17*19.

The result? I was able to come up with the same solution in about three minutes—that's 57% faster than my iBook could solve the problem with my "vastly improved" Ruby algorithm. Go figure.

This whole process taught me that there's a big difference between solving the problem and developing an elegant solution. I'm working on the latter.

If you're curious about what I did, check my spec on Github.