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
    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?

  • \$\begingroup\$ Have you solved the problem on PE? Have you looked at the attached pdf (see i.sstatic.net/WLwim.png ) that goes into the math for a better implementation? \$\endgroup\$
    – user22048
    Oct 28, 2013 at 19:46
  • 3
    \$\begingroup\$ Project Euler has its own forum. Once you solve the problem using ANY way that gives you a solution, you get access to the forum for that problem where plenty of other people post their solutions. \$\endgroup\$
    – DXM
    Oct 28, 2013 at 19:52
  • \$\begingroup\$ @ MichaelT the fibLoop function implements the algorithm that is recommended by the site, i was looking for a functional solution which would be as fast as the imperative method, maybe a tail recursive solution \$\endgroup\$
    – firephil
    Oct 28, 2013 at 19:56
  • \$\begingroup\$ @firephil there's a rather elegant solution on page 5 of the PE question #2 forum. Don't know how fast they compare though. \$\endgroup\$
    – user22048
    Oct 28, 2013 at 19:59
  • 1
    \$\begingroup\$ From a programming point of view, the loops is the best you can do. Any better solutions rely on mathematical principles, not programming efficiency. If you're learning to program (or learning a new language), PE is a poor tool, since many of the problems come down to having mathematical knowledge or already knowing a particular algorithm for a solution. \$\endgroup\$
    – Sean McSomething
    Oct 28, 2013 at 23:21

1 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)


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


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


2 + 8 + 34 = 44 = (89 - 1) / 2
  • \$\begingroup\$ still you have to iterate on the collected values and add them though.And i think adding is more efficient than calculating the values directly if you had started for an initial value say fib(5000) would have more efficient to jump there but with this given problem you have to start from 1 so its faster to start calculating from fib(1) \$\endgroup\$
    – firephil
    Oct 28, 2013 at 20:27
  • 2
    \$\begingroup\$ @firephil: no, you don't have to iterate. The sum of even fibonacci numbers is equal to the sum of two geometric series. There is a closed form expression for the sum of a geometric series: sum(0..n) x^n = (x^(n+1)-1)/(x-1). \$\endgroup\$
    – kevin cline
    Oct 28, 2013 at 23:21
  • \$\begingroup\$ thnx i see what you mean now \$\endgroup\$
    – firephil
    Oct 29, 2013 at 17:58
  • \$\begingroup\$ @kevin cline it is more expensive to compute the closed form than a simple iteration or tail recursive algorithm. It may seem the closed form is faster but its not. I have performed measurements. Also you run into accuracy problems because you need to calculate the sqrt(5) which in most languages it is calculated with "double" precision \$\endgroup\$
    – firephil
    Aug 8, 2014 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.