Project Euler - Problem 2

Monday, May 5, 2025

This is the second post in my new Project Euler series. I recently wrote about Problem 1. Shockingly, I’m still at it.

The GitHub repo is here: rwgrier/swift-project-euler

Let’s dive in.

The second problem states:

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.

So, it’s a Fibonacci problem. That’s familiar territory. I’ve written about the Fibonacci Sequence in 2014 and again in 2016. Those posts covered a variety of ways to calculate Fibonacci numbers at a given index, from brute force to memoization to using my Jedi-math tricks.

For this one, I’m going with Binet’s Formula. It’s elegant and good enough for what we need here. (If I were doing this in a coding interview, I’d reach for memoization like I showed in the 2016 post.)

To reuse later, I wrapped it all in a FibonacciGenerator:

struct FibonacciGenerator {
    private let sqrt_5: Double
    private let phi: Double

    init() {
        sqrt_5 = sqrt(Double(5))
        phi = ((1 + sqrt_5) / 2)
    }

    func fibonacci(at index: Int) -> Int {
        guard index >= 2 else {
            return index
        }

        let doubleIndex = Double(index)

        // x(n) = (Phi^n - (-Phi)^-n) / √5
        let numerator = pow(phi, doubleIndex) - pow((-1.0 * phi), (-1.0 * doubleIndex))
        return Int(numerator / sqrt_5)
    }
}

It should be noted here that Binet’s Formula can produce inaccurate Fibonacci numbers at larger indices (over 71) because of rounding issues (source). But we shouldn’t encounter that issue for this problem. If we do in the future, I’ll adjust the algorithm.

Now that we can generate Fibonacci numbers, solving the problem is three simple steps:

  1. Generating numbers up to the limit (4 million)

  2. Filtering for even values

  3. Summing the result

Here’s the function to generate the Fibonacci sequence up to a max:

private func generateFibonacciNumbersUpTo(_ max: Int) -> [Int] {
    let generator = FibonacciGenerator()
    var numbers: [Int] = []
    var index: Int = 0
    var fibonacci = 1

    while fibonacci <= max {
        defer { index += 1 }
        fibonacci = generator.fibonacci(at: index)

        guard fibonacci <= max else { break }
        numbers.append(fibonacci)
    }

    return numbers
}

This method loops through calculating Fibonacci numbers until it reaches the maximum. Then, it returns an array of Fibonacci numbers.

Then, summing the even-valued terms is easy:

func sumEvenFibonacci(_ max: Int) -> Int {
    generateFibonacciNumbersUpTo(max)
        .filter { $0.isMultiple(of: 2) }
        .reduce(0, +)
}

Done and done.

Next up, Problem 3. Maybe.

Older • Newer