Time for the second Project Euler post!

Project Euler #2

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. Project Euler #2

So it looks like we need to find all of the even numbers in the Fibonacci sequence, and then add them all together.

Calculating the Fibonacci Sequence

It seems like a good place to start would be finding the Fibonacci Sequence up to the limit specified by the question. The next number in the sequence is found by adding the previous two terms. The question shows that the sequence starts with 1 (actually, it starts with 0 followed by two ones, but we'll follow the problem) and the following number is 2. We'll specify our starting points in the code.

1
2
3

num = 2
previous_num = 1
new_num = num + previous_num

The code above will set new_num to 2 + 1 which is 3, the next number in the sequence. However, this code can only ever find the next number after the first two numbers. We're going to want to keep going until we hit the limit. This seems like the perfect time for an until loop.

1
2
3
4
5

num = 2
previous_num = 1
until num >= limit
  new_num = num + previous_num
end

Now this code has a few problems. First, limit is never defined. We can fix that by wrapping our code in a function that has the limit as a parameter.

1
2
3
4
5
6
7

def even_fibonacci_sum(limit)
  num = 2
  previous_num = 1
  until num >= limit
      new_num = num + previous_num
  end
end

Our code still has a major issue. The loop will continue forever since we are never changing the value of num. Since we also don't change the value of previous_num, new_num will always be three, so this code doesn't get us any further in the Fibonacci sequence. We need to update the previous_num as well as the current num in order to keep going in the sequence.

1
2
3
4
5
6
7
8
9

def even_fibonacci_sum(limit)
  num = 2
  previous_num = 1
  until num >= limit
      new_num = num + previous_num
      previous_num = num
      num = new_num
  end
end

Now we're finding all numbers in the Fibonacci sequence up to the limit!

Calculating the Sum

Finding all the numbers in the Fibonacci sequence up to the limit is great, but we're not actually doing anything with those numbers. The problem specifies that we're going to ultimately want the sum of the even numbers, so we should probably keep track of that as we go along.

1
2
3
4
5
6
7
8
9
10
11
12
13

def even_fibonacci_sum(limit)
  num = 2
  previous_num = 1
  sum = 0
  until num >= limit
  if num.even?
      sum += num
  end
      new_num = num + previous_num
      previous_num = num
      num = new_num
  end
end

So now we check if the nummber is even and if it is, add it to our sum, all we need to do now is make sure we return that sum, which in Ruby is generally done implicitely.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def even_fibonacci_sum(limit)
  num = 2
  previous_num = 1
  sum = 0
  until num >= limit
  if num.even?
      sum += num
  end
      new_num = num + previous_num
      previous_num = num
      num = new_num
  end
  sum
end

Arriving at a Solution

To get the solution, run your code! In the terminal, running ruby file_name_here.rb with whatever you named the file that you are coding in, will display the soluton to the terminal screen. When you think you have a solution, you make sure to submit it here.

If you feel that you have a better solution, post a gist to it in the comments!