Better way of calculating Project Euler #2 (Fibonacci sequence)

Question

Even Fibonacci numbers

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.

object Problem_2 extends App {
    def fibLoop():Long =
    {
        var x = 1L
        var y = 2L
        var sum = 0L
        var swap = 0L

        while (x < 4000000)
        {
            if (x % 2 ==0) sum += x
            swap = x
            x = y
            y = swap + x
        }
        sum
    }
    def fib:Int = {
        lazy val fs: Stream[Int] = 0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2)
        fs.view.takeWhile(_ <= 4000000).filter(_ % 2 == 0).sum
    }

    val t1 = System.nanoTime()
    val res = fibLoop
    val t2 = (System.nanoTime() - t1 )/1000 
    println(s"The result is: $res time taken $t2 ms ")
}

Is there a more functional way of calculating the Fibonacci sequence and taking the sum of the even values below 4 million?

Is the imperative method 1000x faster?

Answer 1

No iteration is required to calculate this result.

Every third Fibonacci number is even. The Fibonacci numbers can be expressed in closed form as:

Fib(n) = 1/sqrt(5) * (phi^n - psi'^n)

where

phi = (1 + sqrt(5) / 2)

and

psi = (1 - sqrt(5) / 2)

F(n) is even when n is a multiple of 3.

Therefore the sum of even fibonacci numbers is equal to the sum of two geometric series, and can be calculated directly and exactly.

P.S. A little experimentation shows that

sum(i=0..n) Fib(3*i) = (Fib(3*n + 2) - 1) / 2

e.g.

2 + 8 + 34 = 44 = (89 - 1) / 2