Problem Statement
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.
Solutions
Recursive Solution:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Recursive solution | |
| let eulerProblem2Answer'' = | |
| let maxF = 4000000 | |
| let rec computeSum f1 f2 sum = | |
| match f1 + f2 with | |
| | n -> computeSum f2 n sum | |
| | n when n%2 = 0 -> if (n<maxF) then (computeSum f2 n (sum+n)) else sum | |
| computeSum 0 1 0 |
Using infinite Fibonacci sequence:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let eulerProblem2Answer = | |
| (0,1) | |
| |> Seq.unfold (fun (f1,f2) -> Some(f2, (f2, f1+f2))) // Fibonacci Sequence | |
| |> Seq.takeWhile(fun x -> x < 4000000) // Taking upto Max Fibbonacci | |
| |> Seq.filter (fun x -> x%2=0) // Filtering only even numbers | |
| |> Seq.sum // computing sum |
A bit shorter version can be derived using Seq.SumBy:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let eulerProblem2Answer' = | |
| (0,1) | |
| |> Seq.unfold (fun (f1,f2) -> Some(f2, (f2, f1+f2))) | |
| |> Seq.takeWhile(fun x -> x < 4000000) | |
| |> Seq.sumBy (fun x -> if (x%2)=0 then x else 0) // using SumBy with a projection |
Result
> val eulerProblem2Answer : int = 4613732 val eulerProblem2Answer' : int = 4613732 val eulerProblem2Answer'' : int = 4613732
adilakhter λ 