Project Euler #2

2023-05-09

A good way to hone one's skills in a particular programming language is to do a collection of exercises on Project Euler. Project Euler is a popular website that hosts a set of fun challenges meant to be solved using programming. Problem 2, the focus of this post, asks the following of us:

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

A simple, straightforward, non-modular example of this in Clojure looks something like this:

(defn euler-2 [n]
  (loop [i 1 j 1 acc 0]
    (if (< j n)
      (if (even? j)
        (recur j (+ i j) (+ acc j))
        (recur j (+ i j) acc))
      acc)))

But a more elegant and reusable solution would be:

(defn fibs
  ([] (fibs 0 1))
  ([n m] (cons (+ m n) (lazy-seq (fibs m (+ m n))))))

(defn euler-2 [n]
  (reduce + (filter even? (take-while #(< % n) (fibs)))))

The fibs function returns an infinite lazy sequence of the Fibonacci numbers. This means we aren't adding the unnecessary time complexity of calculating the entire list of Fibonacci numbers up to four million and then sifting through that list.

An even better solution would be to avoid having to filter the even terms like so:

(defn even-fibs
  ([] (even-fibs 0 2))
  ([n m] (cons m (lazy-seq (even-fibs m (+ (* 4 m) n))))))

(defn euler-2 [n]
  (reduce + (take-while #(< % n) (even-fibs))))

This solution relies on a pattern within the even Fibonacci numbers which can be seen as follows:

Let f(n) denote the nth Fibonacci number.

And let f₂(n) denote the nth even Fibonacci number.

We know that f(n+2) = f(n+1) + f(n) by definition.

If you look at the sequence of Fibonacci numbers, you may see a pattern regarding the even numbers:

1 1 2 3 5 8 13 21 34 55 89 144

That is, that there is an even number every 3 terms.

We can show that this pattern repeats infinitely by seeing that at any given even number, the next number will be odd because the sum of an odd and even number is always odd. The same goes for the next number after that. But the sum of two odd numbers is even, which repeats the cycle.

A mathematical way to put this identity would be

f₂(n) = f(3n)

And consequently,

f₂(n+1) = f(3n+3)

f₂(n+2) = f(3n+6)

By expanding these equalities with the Fibonacci definition and some algebra, we find that

f₂(n+2) = 4f₂(n+1) + f₂(n)

Which is the identity used in the algorithm.