## n(n+1)/2

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

$1+2+3+\cdots+n = \dfrac{n(n+1)}{2}$.

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.

Tags: ,

### 2 Responses to “n(n+1)/2”

1. ericfinster Says:

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

2. Problem 1 – nah « Leonhard Euler’s Flying Circus Says:

[…] 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 […]