Euler 001- Starting out Easy

At least something to start the blog with.

Project Euler problem #1; sum all natural numbers less then 1000 that are multiples of 3 or 5. Natural numbers meaning positive integers. The simplest way to go about this is a for loop with a sum, something akin to:

int sum=0;
for(int i=1; i<1000; i++)  
    if(i%3==0 || i%5==0)

Which gives us a nice and specific answer, which is correct. Fun optimization side of this:

You can consider the sum of all 3’s to be 3*sum(1..333), which can be computed as 3*(333*332/2 + 333), if math holds.

Similarly, sum of 5 is 5*sum(1..199) = 5*(199*198/2 + 199).

Next, you need to determine the sum of natural numbers divisible by 15: 15*sum(1..66)=15*67*66/2;

Finally, take the sum of the first two values, and subtract from that the last value. In this case: 166833 + 99500 – 33165 = the answer. This follows from a little too much math, and a bit of set theory: numbers divisible by 15 are counted in both the 3 and 5 cases, effectively double counted. We subtract one of these double counts to end up with a single count of all numbers; and, an O(1) solution.


Leave a Reply

Allowed HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>