Project Euler Problem 1

prob.py

"""
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.
"""

cap = 1000
total = 0

for i in range(1,cap):

    if (i % 5 == 0) or (i % 3 == 0):
        total = total + i

print "First Answer:", total

"""
1,2,3,4,5,6,7,8,9,10

1,10 = 11
2,9  = 11
3,8  = 11
4,7  = 11
4,6  = 11

5 pairs that always add to 11

55 is the sum of all of them, 5(5 pairs that all add up to 11)

5 is half of 10
and 11 is 10 + 1

10(10+1)/2 = 55

There will always be half of N the pairs
all the pairs will add up to 1 + N

N/2 = Number of pairs
N + 1 is what each pair adds up to

N(N+1)/2

In the 3 and 5 case we need to look at the number of pairs divisible by 3 added to the
number of pairs divisible by 5

1,2,3,4,5,6,7,8,9,10
3 + 6 + 9 = 15

10(10+1)/2     --> 1 + 2 + 3 + 4...
3 * 10(10+1)/2 --> 3 + 6 + 9 ...

N should be the highest number less than p divisible by n

N = 9/3 ---> 3
p = 9
n = 3
3 * (9/3) * ((9/3) + 1) / 2
3 * 3 * 4 /2 = 18

N = 9/5 ---> 1
p = 9
n = 5
5 * (9/5) * ((9/5) + 1) / 2
5 * 1 * 2 / 2 = 5


N = p/n
p = 999
n = 15
15 * (999/15) * ((999/15) + 1) / 2


15 * 66 * 67  / 2 = 33165
5 * 199 * 200 / 2 = 99500
3 * 333 * 334 / 2 = 166833

"""

def divby(n,p):
    return n * (p/n) * (p/n + 1) / 2

print "Second Answer:", divby(3,999) + divby(5,999) - divby(15,999)