Project Euler: Problem 1

http://projecteuler.net/index.php?section=problems&id=1

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.

The simplest, and naive, approach is to iterate over all numbers less than N (in this case, 1000) and test against modulo 3 and 5.

def f1(n):
    total = 0
    for i in xrange(1,n):
        # It's slightly quicker to check against 3 first 
        if i%3 is 0 or i%5 is 0:
            total += i
    return total

This yields the correct answer, but is relatively slow.  Can we do better?  Yes!  Instead of iterating over all numbers from 1 to N, let's use the arithmetic series equation.

def f3(n):
    total = 0

    # Count the number of terms with d=3
    c = (n-1)//3
    # Add in the arithmetic series for d=3
    total += c*(6 + 3*(c-1) )/2

    # Count the number of terms with d=5
    c = (n-1)//5
    # Add in the arithmetic series for d=5
    total += c*(10 + 5*(c-1) )/2

    # Count the number of terms with d=15
    c = (n-1)//15
    # Subtract out the (double counted) series for d=15
    total -= c*(30 + 15*(c-1) )/2

    return total

On my set-up, f1(1000) returns in about 1.99e-04 seconds and f3(1000) returns in about 1.70e-6 seconds.  Furthermore, f1(n) scales as O(n) while f3(n) scales as O(1).  Nice!