Problem 2: Even Fibonacci Numbers

Problem

• Link to the problem

Solution

See it on GitHub.

//* Problem 2: Even Fibonacci Numbers
//*
//* 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.

//! time complexity: O(log n)
//! where n is the maximum value
use euler::prelude::*;

const MAX: u32 = 4_000_000;

fn solve() -> Solution {
    // every third fibonacci number is even.
    // see notes/p2.md for proof
    let mut sum = 0;
    let (mut a, mut b) = (2, 8);

    while a <= MAX {
        sum += a;
        (a, b) = (b, 4 * b + a);
    }

    solution!(sum)
}

problem!(
    2,
    solve,
    "1f5882e19314ac13acca52ad5503184b3cb1fd8dbeea82e0979d799af2361704"
);