365 Days of Code - Day 013

After yesterday’s experience with Project Euler (opens in a new tab), I wanted to keep the momentum going today, and solve the next problem, again with C. I did notice the my LaTeX code blocks are not being rendered, so I’ll need to solve that too. I briefly looked at the Hugo docs (opens in a new tab), and there appears to be some built in solutions to try.

Problem 2 - Even Fibonacci Numbers

Today’s problem summary is as follows:

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.

The Fibonacci sequence (opens in a new tab) is quite famous. It often starts with 0 and 1 (although Fibonacci started with 1 and 2), and these numbers are summed to create our first Fibonacci number, 1. Now, we have 0, 1, 1. Add the last two digits, and now we have our 2. This cycle repeats forever.

One of my favorite movies, Pi (opens in a new tab), references the Fibonacci sequence as part of the plot.

So, we have a Fibonacci problem, which is commonly solved with recursion in Computer Science classes. But, we also have an additional constraint, which is to sum only the even numbers.

An interesting fact about the Fibonacci sequence is that even numbers show up for every third term. We ignore 0, as that is neither even nor odd, and start with 1, 1, which is odd, odd. These numbers add up to 2, which is even, and the cycle repeats.

  • odd + odd = even
  • odd + even = odd
  • even + odd = odd

This can be used to solve the problem with a known mathematical identity, but first, I’ll solve it using a naive approach.

Naive Solution - O(log n)

The naive solution is to calculate all the Fibonacci numbers up to N and sum the even ones. Easy enough, and still pretty fast. In fact, I changed N to long long and ran this up to 4000000000000000000 (four quintillion), and it completes instantly.

c 
#include <stdio.h>

int main() {
  long long a = 0, b = 1, sum = 0;
  const int N = 4000000;
  while (b < N) {
    long long tmp = a + b;
    if (tmp % 2 == 0) sum += tmp;
    a = b;
    b = tmp;
  }
  printf("sum = %lld\n", sum);
  return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <stdio.h>

int main() {
  long long a = 0, b = 1, sum = 0;
  const int N = 4000000;
  while (b < N) {
    long long tmp = a + b;
    if (tmp % 2 == 0) sum += tmp;
    a = b;
    b = tmp;
  }
  printf("sum = %lld\n", sum);
  return 0;
}

This works, and comes up with the right solution. However, is it optimal? There does appear to be a solution with O(log log n) time, which is technically much, much faster than O(log n), but I’m happy with a log n solution.