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.

First Attempt.

I decided to approach this problem with a brute force method for the sake of dipping my toes back into Project Euler. Because the problem is not that complicated, I decided to simply use a for loop to iterate from 0 to less than 1000, keeping a sum of the numbers divisible by 3 and 5.

Time: 23047 nanoseconds

Second Attempt

Another way to calculate the sum would be to make use of arithmetic progressions. We are asked to find the series sum for multiples of 3's and 5's. Because 3 and 5 have 15 in common, we must also subtract the series for 15 from our sum. Additionally, the problem states that we must find the sum below 1000. Therefore, we can use 999 as our upper bounds, as 1000 is a multiple of 5. Our rule for arithmetic progressions is n/2(2a+(n-1)d), where a is the first number in the progression, and d is the distance between the numbers in our progression. This expression can be rewritten in our case to a+(n-1)d=x, and, taking account for computational concurrency and solving for n, n=int((x-a)/d+1). Because we are finding the sums for each progression (3 and 5), we can set a=d and we get n=int(x/d-d/d+1)=int(x/d). The nth, last term, is given by l=a+(n-1)d=d+(int(x/d)-1*d=d*int(x/d).

Combining the first equation with our nth term equation to find the sum, we get S=(n/2)(a+1)=(int(x/d)/2*(d+d*int(x/d)). This can be simplified to S=d*int(x/d)*(1+int(x/d))/2.

Again, our equation must find the sum of multiples of 3's, the sum of the multiples of 5, and subtract the sum of multiples of 15. Thus, our equation becomes S=3*int(999/3)*(1+int(999/3))/2+5*int(999/5)*(1+int(999/5))/2-15*int(999/15)*(1+int(999/15))/2.

Time: 172 nanoseconds

Cheers!