Project Euler: Problem 2

Author

Rahul

Published

January 2, 2025

The render notebook is available at: Project Euler Problem 2

Problem Statement

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, \dots\]

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

Euler, Project. n.d. “Problem 2: Even Fibonacci Numbers.” https://projecteuler.net/problem=2.

Understanding the Problem

First, let us understand the problem structure using recommended structure of Polya (Polya 2014).

Polya, G. 2014. How to Solve It: A New Aspect of Mathematical Method. Princeton Science Library. Princeton University Press.

  1. Understanding the problem:

    • What is given?
      • The Fibonacci sequence starts with 1 and 2.
      • Each subsequent term is the sum of the two preceding ones.
      • We need to consider terms not exceeding 4 million.
    • What is required?
      • To find the sum of even-valued terms in this sequence.
    • What are the constraints?
      • Only consider terms up to 4 million.
      • Only sum the even-valued terms.
    • Can we break it down?
      • Generate Fibonacci sequence up to 4 million.
      • Filter out odd terms.
      • Sum the remaining even terms.

Computation Code Structure

Inputs:

  • Fibonacci sequence starting with terms 1 and 2.
  • Upper limit: 4,000,000.

Outputs:

  • The sum of all even-valued terms in the sequence below 4,000,000.

Constraints:

  • Sequence stops when a term exceeds 4,000,000.

Steps:

  1. Iterate through Fibonacci sequence up to 4,000,000.
  2. Filter the sequence to keep only even-valued terms.
  3. Compute the sum of the filtered terms.
  4. Return the computed sum.

Note: After some experimentation with different methods to generate the Fibonacci sequence to manage integer overflow and stack overflow errors in recursive formulas, I narrowed down to using Binet’s formula. The Binet implementation is adapted from Jan Vanhove’s blog (Vanhove n.d.).

Vanhove, Jan. n.d. “Adjusting to Julia: Generating the Fibonacci Sequence.” https://www.juliabloggers.com/adjusting-to-julia-generating-the-fibonacci-sequence/.

Solution

```{julia}
using .Iterators
"""
    fib_binet(n::Integer) -> BigInt

Calculate the nth Fibonacci number using Binet's formula.

This function uses Binet's formula to compute the nth Fibonacci number.
It's more efficient than recursive methods for large n, but may lose
precision for very large n due to floating-point arithmetic.

Parameters:
    n::Integer : The index of the Fibonacci number to calculate (n ≥ 0)

Returns:
    BigInt : The nth Fibonacci number

Examples:
    julia> fib_binet(10)
    BigInt(55)

    julia> fib_binet(100)
    BigInt(354224848179261915075)

Note:
    This function returns a BigInt to handle large Fibonacci numbers.
    For very large n, consider using methods that don't rely on floating-point arithmetic.
"""
function fib_binet(n::Integer)
1    φ = (1 + sqrt(5))/2
    ψ = (1 - sqrt(5))/2
2    fib_n = 1/sqrt(5) * (φ^n - ψ^n)
3    return BigInt(round(fib_n))
end

```
1
Calculate the golden ratio (φ) and its conjugate (ψ)
2
Apply Binet’s formula to compute the nth Fibonacci number
3
Round the result and convert it to a BigInt for precision 
Main.Notebook.fib_binet
```{julia}
"""
    sum_even_fibonacci(limit::Int) -> BigInt

Calculate the sum of even-valued Fibonacci numbers not exceeding the given limit.

This function generates Fibonacci numbers using Binet's formula, filters for even terms,
and sums them up to the specified limit.

Parameters:
    limit::Int : The upper bound for Fibonacci numbers to consider

Returns:
    BigInt : The sum of even Fibonacci numbers not exceeding the limit

Example:
    julia> sum_even_fibonacci(4_000_000)
    BigInt(4613732)
"""
function sum_even_fibonacci(limit::Int)
    # Create an infinite sequence of Fibonacci terms using Binet's formula
1    fib_sequence = (fib_binet(n) for n in 1:BigInt(typemax(Int)))

    # Take terms until they exceed the limit and collect into an array
2    filtered_terms = collect(takewhile(x -> x <= limit, fib_sequence))

    # Filter even terms and sum them
3    even_sum = sum(filter(x -> x % 2 == 0, filtered_terms))

    return even_sum
end
```
1
Generate an infinite sequence of Fibonacci numbers using the fib_binet function (assumed to be defined elsewhere).
2
Use takewhile to collect Fibonacci numbers up to the specified limit.
3
Filter the even terms and calculate their sum. 
Main.Notebook.sum_even_fibonacci

First draft of annotation generated with the assistance of Perplexity AI, then edited to enhance language specificity and clarity (Perplexity AI 2025).

Perplexity AI. 2025. “Perplexity AI.” https://www.perplexity.ai.

Result

```{julia}
limit = 4_000_000
result = sum_even_fibonacci(limit)
println("The sum of even Fibonacci terms below $limit is: $result")
```
The sum of even Fibonacci terms below 4000000 is: 4613732