# Riddle 2: Even Fibonacci Numbers

To finish our glorious [Fibonacci/Binary Tree Series](https://picolisp-blog.hashnode.dev/picolisp-explored-the-idx-function), let's solve the second task of the Euler Project. 

----------------------------------

### Task description

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


------------------

This one is pretty straightforward, if not to say a little bit boring. "Values below four million" means that we will need 32 iterations, so any of our [Fibonacci solutions](https://picolisp-blog.hashnode.dev/the-fibonacci-sequence) will work.

Let's pick our favorite solution from the Fibonacci coding examples (for example the iterative one):

```
(de fib (N)
   (let (A 0  B 1)
      (do N
         (swap 'B (+ (swap 'A B) B)) ) ) )
```
We need two modifications: Instead of a fixed number of iterations, we want the loop to stop if the **next** fibonacci number exceeds 4 Million. So let's replace the ``N`` argument by the ``Max`` and the ``do`` by ``while``:

```
(de sumEvenFib (Max)
    ...
    (while (< (+ A B) Max)
```
Secondly, we want to add up only even numbers and return this ``Sum`` in the end. A number is even if it's dividable by 2, i. e. the modulo is zero: ``(=0 (% B 2))``. 
```
(let Sum 0
     ...
    (when (=0 (% B 2)) 
        (inc 'Sum B) 
```

Minor optimization: Since all numbers are represented internally in **binary**, you could also check if the lowest **bit** of the binary representation of ``B`` is 1 by using the ``bit?`` function:

``` 
(unless (bit? 1 B)
```

And then we have it. This is the final function:

```
(de sumEvenFib (Max)
   (let (A 0  B 1 Sum 0)
         (while (< (+ A B) Max)
            (swap 'B (+ (swap 'A B) B))
            (when (=0 (% B 2)) 
               (inc 'Sum B) ) ) ) )
```

After running ``(prinl (fibo 4000000))``, we get the result.

The final script can be downloaded [here](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_2-Even-Fibonacci-Numbers.l). You can run it with ``pil <filename>`` from the command line.


-----------------------

There is some room for some further optimization, by using the fact that only every third number is even, or by making some clever substitutions in the numeric version. Check out this solution for some inspiration: https://www.xarg.org/puzzle/project-euler/problem-2/

However, since we only need 32 iterations anyway, it is not really worth the trouble.

------------------

With this post, we'll be pausing the algorithmic/mathematical examples for a while. The next month will be dedicated to a new topic: Web Application Programming!

------------------

# Sources

https://www.xarg.org/puzzle/project-euler/problem-2/   
https://projecteuler.net/index.php?section=problems&id=2