Project Euler #2 – Even Fibonacci Numbers

Problem Overview

• Consider the Fibonacci sequence defined in this problem as:
  • fib(0) = 1, fib(1) = 2
  • fib(n) = fib(n-1) + fib(n-2) for n ≥ 2


• The sequence begins: 1, 2, 3, 5, 8, 13, 21, 34, ...


• Goal: Find the sum of the even-valued terms whose values do not exceed four million.

C Solution

#include <stdio.h>
#include <stdint.h>

/// Even Fibonacci Numbers

// Fibonacci Series defined in the Problem 2:
// fib(0) = 1
// fib(1) = 2
// fib(2) = 3
// fib(3) = 5
// fib(4) = 8
// ...
// fib(n) = fib(n-1) + fib(n-2)

#define FOUR_MILLION (4000000ul)

uint64_t fib(uint64_t n)
{
    if (n == 0)
    {
        return 1;
    }

    if (n == 1)
    {
        return 2;
    }

    return fib(n-1) + fib(n-2);
}

uint64_t solve()
{
    uint64_t sum = 0;
    uint64_t n = 0;
    while (1)
    {
        uint64_t term = fib(n);
        if (term > FOUR_MILLION)
        {
            break;
        }
        if (term % 2 == 0)
        {
            sum += term;
        }
        n++;
    }
    return sum;
}

int main()
{
    printf(
        "The sum of the even-valued fibonacci numbers whose values do not exceed four million: %lu\n",
        solve());
    return 0;
}

1. Key Ideas


• Use a recursive function fib that matches the problem's definition of Fibonacci numbers starting with 1 and 2.
• Generate terms one by one: fib(0), fib(1), fib(2), ...
• Stop when the current term is greater than 4,000,000.
• Accumulate only the even-valued terms in a running sum.



2. The fib Function



uint64_t fib(uint64_t n)
{
    if (n == 0)
    {
        return 1;
    }

    if (n == 1)
    {
        return 2;
    }

    return fib(n-1) + fib(n-2);
}

• Base cases:
  • fib(0) = 1
  • fib(1) = 2
• For n ≥ 2, compute fib(n) as the sum of the two previous terms.
• Return type uint64_t avoids overflow for this range of values.



3. The solve Function



uint64_t solve()
{
    uint64_t sum = 0;
    uint64_t n = 0;
    while (1)
    {
        uint64_t term = fib(n);
        if (term > FOUR_MILLION)
        {
            break;
        }
        if (term % 2 == 0)
        {
            sum += term;
        }
        n++;
    }
    return sum;
}

• sum stores the running total of even Fibonacci numbers.
• n indexes Fibonacci terms (fib(0), fib(1), ...).
• Each loop:
  • Compute the current term term = fib(n).
  • If term > 4,000,000, stop.
  • If term is even, add it to sum.
  • Increase n and continue.
• Returns the final sum.



4. main and Output



int main()
{
    printf(
        "The sum of the even-valued fibonacci numbers whose values do not exceed four million: %lu\n",
        solve());
    return 0;
}

• Calls solve() and prints the result in a descriptive sentence.
• Returns 0 to indicate success.



5. Complexity and Possible Improvement


• The recursive Fibonacci implementation is exponential in general, but here it is acceptable because the sequence crosses 4 million in only a few dozen terms.
• For practice, you could also implement an iterative Fibonacci generator that builds each term from the previous two without recursion.

Common Lisp Solution

1. Problem Setup


• The task is the same: sum all even-valued Fibonacci numbers not exceeding four million.
• In Lisp, we can elegantly express iterative computations using the loop macro.



2. Full Lisp Solution

(defvar *four-million* 4000000)

(defun sum-even-fibonacci-numbers (upper-bound-inclusive)
  (loop for a = 1 then b
        and b = 2 then (+ a b)
        while (<= a upper-bound-inclusive)
        when (evenp a) sum a))



• *four-million* is defined as a global constant holding the upper bound.
• sum-even-fibonacci-numbers performs the iteration and returns the total sum.



3. Understanding the loop Construct


• loop is a powerful macro in Common Lisp for iteration and accumulation.
• This version defines two variables at once:

  for a = 1 then b
  and b = 2 then (+ a b)
  

  • a starts at 1 and becomes b in each iteration.
  • b starts at 2 and becomes (+ a b) each time.
  • Together they generate the Fibonacci sequence: 1, 2, 3, 5, 8, 13, ...


• The termination condition:

  while (<= a upper-bound-inclusive)
  

  • Stops the loop once the current term a exceeds the given upper bound.


• Conditional summation:

  when (evenp a) sum a
  

  • (evenp a) checks if a is even.
  • If true, a is added to the cumulative sum.



4. Example Evaluation

* (sum-even-fibonacci-numbers *four-million*)
4613732



• The result 4613732 matches the correct answer from Project Euler #2.
• The loop handles both Fibonacci generation and even filtering in one compact form.



5. Highlights


• No recursion or extra data structures are required — just pure looping and accumulation.
• The loop construct combines initialization, update, condition, and summation seamlessly.
• The use of for a ... and b ... keeps both Fibonacci terms in sync each iteration.



6. Performance


• This solution runs in O(k) time, where k is the number of Fibonacci terms up to four million.
• In practice, it finishes instantly since there are only a few dozen iterations.