To finish our glorious Fibonacci/Binary Tree Series, 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 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. 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!
Top comments (0)