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.
https://projecteuler.net/problem=1
The cool thing about this problem is that it doesn’t need any programming at all. Just some fun with summations.
A summation is a convenient and compact way to express sums such as 1+2+3+...+n. We start at 1 and end at n. These are known as the bounds of summation. Each term in the sum is being incremented by one. We can write the sum as \sum_{i=1}^{n}i. The variable i is known as the index of summation. It increments by one for each term of the sum, starting at 1 and stopping at n. If we wanted to add the numbers 1-10, we write \sum_{i=1}^{10}i. That’s much more graceful than writing 1+2+3+4+5+6+7+8+9+10.
What if we wanted to add only the even numbers in 1-10? We have to rewrite the summand so that each i represents an even number. Easy enough: \sum_{i=1}^{10}2i. Multiplying by 2 forces i to be even. But, there’s a problem with the bounds of summation. Trying i=10 gives 20. That’s overshooting! The fix is finding the largest integer i such that 2i\le10. Some quick algebra gives us i=5. The sum of the even numbers from 1-10 is properly written as \sum_{i=1}^{5}2i.
Expanding that gives (2*1)+(2*2)+(2*3)+(2*4)+(2*5). We then can factor out 2: 2*(1+2+3+4+5). This lets us rewrite the sum \sum_{i=1}^{5}2i as 2*\sum_{i=1}^{5}i.
Writing sums is one thing, but what about evaluating them? Enter Carl Friedrich Gauss. Here’s a cool story of how a young Gauss recognized a quick way to solve \sum_{i=1}^{100}i. Long story short, he found that
\sum_{i=1}^{n}i =\frac{n(n+1)}{2} \tag{1}But what if the summand is different? The strategy is to use properties of summation to transform the summand to just i (or other forms for which closed-form expressions are known).
Returning to the problem, we just need to express multiples of 3 or 5 in the right way. How do we transform 1,2,3,... to the multiples of 3: 3,6,9,...? By multiplying i by 3! We’re only interested in multiples below 1000 so we need to make sure i stops at 333 since 3*333 is 999. Same idea for 5, except that the upper bound is 199.
Our sum of multiples of 3 and multiples of 5 is:
\sum_{i=1}^{333}3i+\sum_{i=1}^{199}5iNot so fast! Note that the problem is asking for multiples of 3 or 5. When we hit multiples of 15 (3*5), they get counted for both sums. So, we need to take that out.
\sum_{i=1}^{333}3i+\sum_{i=1}^{199}5i-\sum_{i=1}^{66}15iWe can factor out the constants:
3\sum_{i=1}^{333}i+5\sum_{i=1}^{199}i-15\sum_{i=1}^{66}i \tag{2}Applying Equation 1 to Equation 2 gives:
3*\frac{333(333+1)}{2}+5*\frac{199(199+1)}{2}-15*\frac{66(66+1)}{2} \tag{3}Punching Equation 3 into a calculator spits out 233168, the sum of all multiples of 3 or 5 below 1000. Ta-da! No programming needed! Now, to be fair, doing the algebra and operating the calculator took me 5 minutes. Telling Python to do
sum([i for i in range(1,1000) if i % 3 == 0 or i % 5 == 0])
takes only milliseconds!