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. Find the sum of all the multiples of 3 or 5 below 1000.
We could just brute force this, but from the legend of Gauss in his baby math class that we can get such consecutive sums of multiples easily:
$$\sum_{i=1}^{n} i = \frac{n (n+1)}{2}$$Let $N$ be the upper limit (e.g. 10 or 1000)
We can split this up as follows:
$$3\sum_{i=1}^{a} i + 5\sum_{i=1}^{b} i - 15\sum_{i=1}^{c} i = \frac{3}{2}a (a+1) + \frac{5}{2}b (b+1) - \frac{15}{2}c (c+1) $$where $$a = \lfloor \frac{N-1}{3} \rfloor \\ b = \lfloor \frac{N-1}{5} \rfloor \\ c = \lfloor \frac{N-1}{15} \rfloor$$
The first term accounting for the 3 multiples, the second the 5, and the third subtracting for the numbers which are multiples of both 3 and 5.
We could similarly handle more multiples.
In [2]:
def s(x):
return (x*(x+1))/2
def prob1(N):
a = floor((N-1)/3)
b = floor((N-1)/5)
c = floor((N-1)/15)
return 3*s(a) + 5*s(b) - 15*s(c)
In [3]:
prob1(10)
Out[3]:
In [4]:
prob1(1000)
Out[4]:
In [ ]: