Project Euler Problem #1:

For those who like math and want to learn a programming language, I can think of no better resource than Project Euler. Project Euler contains a free database of over 600 math problems. While the problems are all technically do-able by hand, it is expected that each will be solved with a computer program. This program should be able to solve the problem in less than a minute.

The problems on Project Euler range in difficulty from beginner computer science questions to very advanced math questions. They tend to get progressively more difficult.

For an example of an easier Project Euler question, look no further than Problem #1: Project Euler’s take on the classic “FizzBuzz” interview question.

Project Euler Problem 1: Multiples of 3 and 5
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.

Here are two solutions I found to Project Euler’s version:

Solution #1: Basic Iterative Approach

In this approach, we simply iterate through all numbers i from 1 to 999. If i is divisible by 3 or 5, we add i to a running total, otherwise, we do nothing. Here is the result when this approach is implemented in Python 2.7:

'''
 Author: Walker Kroubalkian
 The Iterative Approach to Project Euler Problem #1
 '''

 import time

 def projectEulerProblemOne(n):
     total = 0
     for i in range(1,n):
         if(i%3==0 or i%5==0):
             total+=i
     return total

 start = time.time()
 print projectEulerProblemOne(1000)
 print("--- %s seconds ---" % (time.time() - start))

 '''
 Prints
 233168
 --- 0.000103950500488 seconds ---
 for input of n = 1000
 '''

Solution #2: Formulaic Approach

While the Iterative approach is fine for solving this problem, it is actually possible to solve this problem with a formula.

Remembering that the sum 1 + 2 + 3 + . . . + n = n(n+1)/2, we can add up all multiples of 3 less than or equal to 3n with the similar expression: 3 + 6 + 9 + . . . + 3n = 3(1 + 2 + 3 + . . . + n) = 3n(n+1)/2. Similarly, we can add up all multiples of 5 less than or equal to 5n with the expression 5n(n+1)/2. If we use these expressions to add up all multiples of 3 and 5 less than 1000, we will add all multiples of 3 and 5 twice, so we must subtract the multiples of 15 with the expression 15n(n+1)/2. Doing so, we get the following formulaic program:

'''
Author: Walker Kroubalkian
The Formulaic Approach to Project Euler Problem #1
'''

from math import floor
import time

def projectEulerProblemOne(n):
    numberThrees = floor((n-1)/3)
    numberFives = floor((n-1)/5)
    numberFifteens = floor((n-1)/15)
    
    addThrees = 3*numberThrees*(numberThrees+1)/2
    addFives = 5*numberFives*(numberFives+1)/2
    addFifteens = 15*numberFifteens*(numberFifteens+1)/2start = time.time()

    return addThrees + addFives - addFifteens
    
print projectEulerProblemOne(1000)
print("--- %s seconds ---" % (time.time() - start))

'''
Prints
233168
--- 2.19345092773e-05 seconds ---
for input of n = 1000
'''

As expected, the formulaic approach tends to be faster for solving this problem. With this approach, it is even feasible to do this question by hand.

I will try to post a solution to a Project Euler problem each day for as long as I can.

Thanks for reading my first blog post!