My new approach to Problem 1 is different from Eric’s. We all know the formula

.

We can use this formula to very quickly add the multiples of 3 between 1 and 999, namely, add all the integers between 1 and 333, and then multiply by 3. Similarly, we can add the integers between 1 and 195 and then multiply by 5 to get the sum of all multiples of 5 between 1 and 999. Putting those together, we’ve double-counted the multiples of 15, so we subtract the multiples of 15 to get the sum of all multiples of 3 or 5 between 1 and 999.

In general, if you had more divisors, you’d have to use some sort of alternating sum/inclusion-exclusion principle argument to get rid of the stuff you double/triple/quadruple/etc.-counted.

a=3
b=5
c=999
d=a*b
e=c//a
f=c//b
g=c//d
a*e*(e+1)/2+b*f*(f+1)/2-d*g*(g+1)/2

I did not write code to handle more divisors. I suppose you could just stick my equation into Eric’s code, and that would work.

### Like this:

Like Loading...

*Related*

Tags: cmd, prob1

This entry was posted on May 15, 2009 at 11:51 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

May 15, 2009 at 12:34 pm |

Hey, that’s much better. Cool idea. I’ll try and get that into my code when I get back from camping this weekend.

May 18, 2009 at 12:17 am |

[…] should mention that Chris’ recent code pointed out to me that you can just subtract one from the upper bound, and then do no any extra […]