Posted on 2019-05-21.

These early Project Euler problems are fairly basic in terms of both the programming and math skills required, but you can still learn interesting things from working on them. I used the opportunity to teach myself a little about Kotlin, and to learn a little math in the pursuit of optimized solutions.

Table of Contents:

• Solution 1: Brute Force
• Solution 2: Only use every third element
• Solution 3: Faster element skipping
• Solution 4: Only generate even elements
• Solution 5: Approximate using the Golden Ratio
• Solution 6: Only use the last two elements
• Solution 7: Closed-form expression

Problem 2: Even Fibonacci numbers

The problem statement from https://projecteuler.net/problem=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.

Solution 1: Brute Force

A straightforward approach is:

1. Use variables to remember the two most recent numbers in the Fibonacci sequence, and a variable to record the current sum.
2. In a loop:
   1. Check if the current number in the sequence is an even number. If it is, add it to the sum.
   2. Calculate the next number in the sequence, and update the variables containing the most recent numbers accordingly.
   3. Continue until you reach a number greater than four million.

Here’s the code:

fun main() {
    var prev = 1
    var cur = 2
    var sum = 0

    while (cur <= 4000000) {
        if (cur % 2 == 0) {
            sum += cur
        }
        val next = cur + prev
        prev = cur
        cur = next
    }

    println(sum)
}

Solution 2: Only use every third element

Consider the first ten elements of the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Notice that (if you ignore 0) every 3rd element is even, and the rest are odd. This pattern will hold for the whole sequence.

This is a consequence of the following facts:

• The sum of two odd numbers is always an even number. (1 + 1 = 2, 3 + 5 = 8, …)
• The sum of an even number and an odd number is always an odd number. (1 + 2 = 3, 2 + 3 = 5, …)
• Each element in the Fibonacci sequence is the sum of the two previous elements.

So, to have an even number in the sequence, it must be preceded by two odd numbers. And two odd numbers will always be followed by an even number.

We can use that to avoid explicitly checking whether a number is even or odd. The loop can use a counter to keep track of how many elements it should skip before the next one that it needs to add to the sum. Here’s the code:

fun main() {
    var prev = 1
    var cur = 2
    var sum = 0
    var skip = 0
    
    while (cur <= 4000000) {
        if (skip == 0) {
            sum += cur
            skip = 2
        } else {
            skip--
        }
        val next = cur + prev
        prev = cur
        cur = next
    }

    println(sum)
}

(I haven’t measured, but I would guess this is a bit slower than the previous solution on a typical computer.)

Solution 3: Faster element skipping

As explained in solution 2, you only need every third element of the Fibonacci sequence. The Project Euler solution overview for this problem shows a more concise and efficient way of using that insight.

The inefficiency in solution 2 is that it still only generates one Fibonacci number per iteration of the loop, so it needs a conditional check to see whether it’s on one of the numbers it should skip or not. Instead, we can hardcode the loop to always generate three Fibonacci numbers and throw away the first two.

Here’s the code:

fun main() {
    var prev = 1
    var cur = 2
    var sum = 0

    while (cur <= 4000000) {
        sum += cur

        val next1 = cur + prev
        val next2 = cur + next1
        val next3 = next1 + next2
        prev = next2
        cur = next3
    }

    println(sum)
}

Solution 4: Only generate even elements

Solution 2 discussed how every third element, and only every third element, of the Fibonacci sequence is an even number. Once you know that, you might wonder whether there’s some formula for directly generating a sequence of even Fibonacci numbers, rather than generating the whole sequence just to throw away two-thirds of it.

The Project Euler solution overview for this problem explains that there is indeed.

Recall that the formula for Fibonacci numbers is:

Fib(n) = Fib(n - 1) + Fib(n - 2)

The formula to get only the even Fibonacci numbers is:

EvenFib(n) = 4 * EvenFib(n - 1) + EvenFib(n - 2)

To prove this, we can start with the following definition:

EvenFib(n) = Fib(3n)

In other words, the Nth element of the sequence of even Fibonacci numbers is the (3 * N)th element of the full Fibonacci sequence. We know that for the reasons explained in solution 2.

Now, we can construct a proof by repeatedly substituting the definitions of EvenFib and Fib into the right-hand side of that equation, until it looks like the formula we’re trying to prove.

Each line of the following diagram shows one step of the proof.

The code to use this formula is simple:

fun main() {
    var prev = 2
    var cur = 8
    var sum = 2
    
    while (cur <= 4000000) {
        sum += cur
        val next = prev + 4 * cur
        prev = cur
        cur = next
    }

    println(sum)
}

Solution 5: Approximate using the Golden Ratio

I learned of this approach from a post by user RudyPenteado on the Project Euler forums.

If you try dividing each number in the fibonacci sequence by the number immediately preceding it, you’ll see that the results start to converge:

As explained on Wikipedia, if you could carry this process out to infinity, it would converge on a number called the Golden Ratio. Since the Golden Ratio (also known as Φ) is an irrational number, there is no exact decimal representation of it. But 1.6180339887 is an approximation.

This can be used in an algorithm for producing the Fibonacci sequence without remembering past values in the sequence:

1. Start at 1.
2. Multiply by Φ.
3. Round to the nearest integer. This is the next number in the sequence.
4. Go back to step 2 and continue as long as desired.

This can be improved a bit since we only actually need every third number in the sequence (as explained in solution 2). Rather than multiply by Φ, throw the result away, multiply by it again, throw the result away, and multiply by it again, we can just multiply by Φ^3.

(There’s a bit of a logical leap there. Doing “multiply by a certain constant and round to the nearest integer” three times is not guaranteed to have the same result as doing “multiply by a certain constant three times and round to the nearest integer”. In fact, if you try to calculate a particular value of Fib(n) by simply calculating Φ^n and rounding at the end, you’ll often get incorrect answers. Nevertheless, rounding once every third product seems to be good enough to get the correct answer for the Euler problem.)

Here’s the code:

import java.lang.Math.round

const val Φ = 1.6180339887 // No, I wouldn't use non-ASCII identifiers in real-word code, don't @ me
const val Φ_CUBED = Φ * Φ * Φ

fun main() {
    var cur = 2
    var sum = 0

    while (cur <= 4000000) {
        sum += cur
        cur = round(cur * Φ_CUBED).toInt()
    }

    println(sum)
}

This is an imprecise solution; it will not give the correct answer once the limit exceeds a certain length. Specifically, using a Φ value of 1.6180339887, I found that calculating Fib(n) by this method of approximation yields an incorrect value at Fib(51). The correct result would be 20,365,011,074, but it yields 20,365,011,073.

But the approach is adequate for the original Project Euler problem, and you could use a more precise value of Φ if you wanted to support a larger range accurately.

Solution 6: Only use the last two elements

I learned about this from a post by user Francky on the Project Euler forums.

Solution 4 shows how to generate only the even elements of the Fibonacci sequence in a loop. On each iteration, it updates a variable that contains the current sum.

Intuitively, it seems like keeping track of the sum might be redundant. Each Fibonacci number is formed by adding the previous two, which are themselves formed by adding previous Fibonacci numbers. So the numbers themselves are already close to being sums of the series.

Proof for the Fibonacci sum formula

In fact, the sum of the first n Fibonacci numbers is equal to Fib(n + 2) - 1.

The proof of this by induction is short:

1. Base case: The sum of the first 1 Fibonacci numbers is, of course, equal to the first Fibonacci number. We know Fib(1) = 1, Fib(3) = 2, and 2 - 1 = 1, so it’s clearly true that Fib(1) = Fib(1 + 2) - 1.
2. Inductive step: We have to prove that Fib(1) + Fib(2) + ... Fib(n) + Fib(n + 1) = Fib(n + 3) - 1, which is done as follows:

Proof for the even Fibonacci sum formula

The above was for the regular Fibonacci sequence. What about the sequence of just evens? The formula for the sum of of the first n even Fibonacci numbers is (EvenFib(n) + EvenFib(n + 1) - 2) / 4.

This, too, can be shown by induction:

1. Base case: EvenFib(1) = 2, EvenFib(2) = 8, and (2 + 8 - 2) / 4 = 2, so yes, EvenFib(1) = (EvenFib(1) + EvenFib(1 + 1) - 2) / 4.
2. 2. Inductive step: We have to prove that EvenFib(1) + EvenFib(2) + ... EvenFib(n) + EvenFib(n + 1) = (EvenFib(n + 1) + EvenFib(n + 2) - 2) / 4, which is done as follows: $$\begin{array}{rlrlr}\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{p}& \mathrm{J}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}& \mathrm{S}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}& & \\ (1)& \mathrm{A}\mathrm{s}\mathrm{s}\mathrm{u}\mathrm{m}\mathrm{e}\mathrm{d}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{o}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{.}& EvenFib(1)+EvenFib(2)+...+EvenFib(n)& =& \frac{EvenFib(n)+EvenFib(n+1)-2}{4}\\ (2)& \mathrm{F}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{F}\mathrm{i}\mathrm{b}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{r}\mathrm{.}& EvenFib(n)& =& EvenFib(n-2)+4*EvenFib(n-1)\\ (3)& \mathrm{U}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}(1)\mathrm{.}& EvenFib(1)+EvenFib(2)+...+EvenFib(n)+EvenFib(n+1)& =& \frac{EvenFib(n)+EvenFib(n+1)-2}{4}+EvenFib(n+1)\\ (4)& \mathrm{A}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}& & =& \frac{EvenFib(n)+EvenFib(n+1)-2}{4}+\frac{4*EvenFib(n+1)}{4}\\ (5)& \mathrm{A}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}& & & \frac{EvenFib(n+1)+EvenFib(n)+4*EvenFib(n+1)-2}{4}\\ (6)& \mathrm{U}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}(2)& & & \frac{EvenFib(n+1)+EvenFib(n+2)-2}{4}\end{array}$$

Code

fun main() {
    var prev = 2
    var cur = 8

    while (cur <= 4000000) {
        val next = prev + 4 * cur
        prev = cur
        cur = next
    }

    val sum = (prev + cur - 2) / 4
    println(sum)
}

Solution 7: Closed-form expression

I learned of this approach from several posts on the Project Euler forums.

There's a way to calculate the `n`th Fibonacci number that does not require any looping or recursion, called Binet's formula:

Note:

• Φ is the Golden Ratio, an irrational constant also discussed in solution 5.
• The brackets indicate rounding to the nearest integer.

The section on Wikipedia about the closed-form expression for the Fibonacci sequence has some information about how this is derived.

We also know that the even numbers in the Fibonacci sequence are regularly spaced: every third element is even. This was explained in solution 2. That means the sequence of even Fibonacci numbers can be defined as EvenFib(n) = Fib(3n), which can now also be calculated without any loops or recursion.

From solution 6 we know that the sum of the first n even Fibonacci numbers is equal to:

So we're really close to being able to calculate the answer to this Euler problem without any loops or recursion. All that's missing is a fast way to determine n. That is, we need a way to find the index of the highest even Fibonacci number that is less than 1000.

As explained on Wikipedia, the equation for Fib(n) can be rewritten to solve for n as follows:

Note:

• These brackets indicate taking the floor, that is, rounding down to the nearest integer.
• In this particular equation, I am hazy about how we know that taking the floor will give an accurate result. I'm also unclear as to whether rounding to the nearest integer (and removing the + 1/2 term) would work just as well. If you understand, I'd enjoy hearing it explained in more detail.

If you plug a Fibonacci number into that formula, you'll get the index of that number in the Fibonacci series.

If you plug any number into it, I think it will give you the index of the largest Fibonacci number that is not larger than the given number. This is a weak point in this solution: I expect the formula to always do that, but I don't currently know how to prove it. It works for the few cases I've tested, at least, though.

Anyway, we can put this all together as follows:

• Write a fib(n) function to calculate the nth Fibonacci number, using Binet's formula.
• Write an evenFib(n) function to calculate the nth even Fibonacci number, which is simply fib(3 * n).
• Write an evenFibSum(n) function to calculate the sum of all even Fibonacci numbers up to and including the nth element in the sequence, using the sum formula above.
• Write a fibIndex(f) function to calculate the index of a given number in the Fibonacci sequence, using the formula above derived from Binet's formula.
(Calculating logs of base Φ is inconvenient, but again as mentioned on Wikipedia, you can calculate the natural log instead and then divide by the natural log of Φ to get the log in base Φ.)
• Write an evenFibIndex(f) function to calculate the index of a given number in the even Fibonacci sequence, which is simply fibIndex(f) / 3.
• Use evenFibIndex to find the index of the last even Fibonacci number before the limit specified in the problem, and then pass that to evenFibSum.

val SQRT_5 = Math.sqrt(5.0)
val Φ = (SQRT_5 + 1.0) / 2.0
val LN_Φ = Math.log(Φ)

fun fib(n: Int) = Math.round(Math.pow(Φ, n.toDouble()) / SQRT_5)

fun evenFib(n: Int) = fib(3 * n)

fun evenFibSum(n: Int) = (evenFib(n) + evenFib(n + 1) - 2) / 4

fun fibIndex(f: Long) = Math.floor(
    Math.log(f * SQRT_5 + 0.5) / LN_Φ).toInt()

fun evenFibIndex(f: Long) = fibIndex(f) / 3

fun main() {
    println(evenFibSum(evenFibIndex(4000000L - 1)))
}

Like solution 5, this is an imprecise approach that will give inaccurate answers beyond a certain threshold; you could switch to using something like the BigDecimal instead of doubles if you need to support more precision. Notice that I replaced the hard-coded Φ value with code to calculate Φ, which will ensure that the Φ value is as precise as possible for the data type being used to store it.

Note that at least as long as we're dealing with longs, this whole approach doesn't really benefit us compared with the looping approaches. There are only 31 even Fibonacci numbers less than 2^63, so generating them by a loop takes very little time.