So I’ve been threatening to do this basically since day 1…
But I think another part of the learning process is explaining things, or sometimes at least why I did what I did…
First of all, the problem:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
Now, first, the key word here is under. But we’ll get to that in a second.
At first, this looks like it can be solved with a simple loop, and really, for this exact problem, it can be, with little concern about cost. However, what if this was changed to 1 million, or 10 million, or 100 million…
Well, on most modern-day computers, looping through 1 to 1,000,000 takes about 2 seconds… 1 to 10,000,000 takes about 20 seconds… while 1 to 100,000,000 takes over 3 minutes… while 2 seconds is not horrendous, 20 seconds is bad, and 200 seconds is down right insufferable – at least from today’s web standards…
The solution for this is simple, and usually overlooked… Its taking a simple equation 3 times and your done.
All this is looking for is the sum of all multiples of 3 under 1000 (so 3+6+9+12…+996+999) and the sum of all multiples of 5 under 1000 (important to note since 1000 is divisible by 5, if we use it, we’ll get the wrong result) (so 5+10+15+20…+990+995). Now, if you remember your high school math, there was this equation that allows you to get the sum off all the consecutive integers that made up a number… so, for example, the sum of the consecutive integers for 10 is 1+2+3+4+5+6+7+8+9+10=55. The formula is
10(11)/2 >> 110/2 = 55. So having that, all we have to do is realize that the sum of 3+6+9+12 (quick example) = 30 is the same as (1+2+3+4)*3 >> 10 * 3…
Now, if that’s the case, then the sum of consecutive multiples of three would be 3 * ((n/3)(n/3+1) / 2), or in this case, we know that 999 is the last, and 333 is 1/3 of that, so
3 * 333 * 334 / 2 = 166833, and the same would be true of for 5 (
5 * 199 * 200 / 2 = 99500). So we would think, at first glance, that our answer is 266333. However, we’d be wrong!
Well, we forgot one thing. In using this equation, every multiple of 15 (3×5) is being added in twice… once for the 3 side of it, and once for the five side of it… so all we have to do is subtract out one of them… so
15 * 66 * 67 / 2 = 33165… Now, if we take
166833 + 99500 - 33165 = 233168, which would be the exact same value our loop gives us…
So if we did this to get the results for 100,000,000 instead of 1000, we’d get our solution in under 1/100th of a second, vs 3 1/3 minutes, and at way fewer CPU cycles, which could be very important for some algorithms you write!
So that is my first foray into Project Euler, and the programming puzzles!
Young and Innocent -Elefante