Problem Description

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.

Analysis

This is an ideal solution for the inclusion-exclusion principle. In general, we sum the numbers divisible by 3 or 5 for all numbers less than n, where n=1000 for this problem. Next, we would need to subtracxt those numbers divisible by 15 because they are counted twice.

This solution is very extensible instead of using brute force that requires loops.

Solution

Runs < 1 second in Python.

def sumn(n,d):
  n=int(n/d)
  return int(n*(n+1) / 2*d)
 
n = 999
print "Answer to PE1 = ",sumn(n,3) + sumn(n,5) - sumn(n,15)

Comments

The formula to sum the counting numbers from 1 to n is: n(n+1)/2. As for n=10; 10*11/2=55