In order to stay fresh with general programming skills I am going to attempt various Project Euler problems and walk through my solutions. For those of you that do not know Project Euler it "is a series of challenging mathematical/computer programming problems." Simply put, it is a great way to practice your computer programming skills.

In this blog I'm going to work on Project Euler problems 1 and 2.

Problem 1: Multiples of 3 or 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.

Breaking down the problem:

It's pretty straightforward. We want all the natural numbers (so positive integers... no decimals) under 1,000 that are multiples of 3 or 5. A multiple is simply "a number that can be divided by another number without a remainder." So, multiples of 3 include 3, 6, 9, 12...

Then we just want to take the sum of all those numbers.

I am going to create a function with 2 arguments:

  1. A list of the numbers we want multiples of (so in this case 3 and 5)
  2. The max number we want (in this case 1000)

The function will then do the following steps:

  1. Initialize a list (sum_list). This is where we will store the multiples of the numbers we are interested in. For the case of this problem, I mean all the multiples of 3 and 5.
  2. Loop through 1 and the max_number (1000 for this particular problem). We'll call this number i.
  3. Loop through each of the dividers (e.g. 3 and 5) and use the modulo operator, %, to determine if the number, i, is even or odd. The modulo operator returns the remainder of a division problem (e.g. 4 % 1 = 1).
  4. If the number i has no remainder when divided by a divider we will .append (or add) it to the sum_list we created earlier.
  5. One problem this creates is there could be duplicates. For example, 15 would show up twice in sum_list as both 3 and 5 go into it. We can solve this by removing duplicates in the sum_list. The set() function is any easy way to do this. The function converts the object into a Python set (one of the 4 major Python data classes along with lists, tuples, and dictionaries). Sets "do not allow duplicate values" so the use of list(set(sum_list)) will convert the sum_list into a set, effectively dropping duplicate values, then converting it back into a list.
  6. The last step is to use the sum() function to calculate the sum of all the multiples stored in sum_list.
def euler_1(dividers, max_number):
    sum_list = []
    for i in range(1, max_number):
        for div in dividers:
            if i % div == 0:
                sum_list.append(i)
    sum_list = list(set(sum_list))
    return(sum(sum_list))

Running our function with the arguments from the question (multiples of 3 and 5 up to 1000) we get an answer of 233,168.

euler_1([3,5], 1000)

233168

Problem 1: Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Breaking down the problem:

This problem will involve 3 parts:

  1. Creating a Fibonacci sequence that stops right before 4,000,000
  2. Sorting out only the even numbers
  3. Finding the sum of all those even numbers

Similar to the first Euler problem, I'm going to create a function that takes two arguments:

  1. The maximum number for the Fibonacci sequence (4,000,000) in this case
  2. And, a boolean variable determining if we want to sort even numbers

The function will then do the following steps:

  1. Create a variable called modulo_div that will allow us to toggle whether we want to sum the even-valued terms (such as in this problem) or odd-valued terms
  2. Create a list, fibonacci, with the first two terms of the Fibonacci sequence (1 and 2)
  3. Create a variable, i, which will serve as an iterator
  4. Put i into a while loop. Then, add together the last two numbers of the fibonacci list and make that sum the value of i. For example, on the first iteration we will sum 1 and 2 making i equal to 3.
  5. As long as the value of i is less than 4,000,000 add it to the end of fibonacci using append(). If the value of i exceeds 4,000,000 do not add it to the list and break the loop.
  6. Once the loop is broken we create a new list, fibonacci_portion. Use a Python list comprehension to go through the fibonacci list and only add even numbers. It will be the same method we used to gather odd numbers in the previous problem (using the modulo operator).
  7. Finally, return the sum of the fibonacci_portion list (so all even numbers in the Fibonacci sequence up to 4,000,000) 
def euler_2(max_number, even = True):
    if even == True:
        modulo_div = 2
    else:
        modulo_div = 1
        
    fibonacci = [1,2]
    i = 1
    while i > 0:
        i = sum(fibonacci[-2:])
        if i > 4000000:
            break
        fibonacci.append(i)
        
    fibonacci_portion = [j for j in fibonacci if j % modulo_div == 0]
    
    return(sum(fibonacci_portion))

Running our function with the arguments from the question (a maximum of 4,000,000 and looking at even numbers) we get an answer of 4,613,732.

euler_2(4000000, even = True)

4613732