n(n+1)/2

by

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.

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: