{"id":261,"date":"2010-07-05T13:27:00","date_gmt":"2010-07-05T18:27:00","guid":{"rendered":"http:\/\/factormystic.net\/blog\/?p=261"},"modified":"2010-07-05T13:27:00","modified_gmt":"2010-07-05T18:27:00","slug":"project-euler-in-fsharp-problem-2","status":"publish","type":"post","link":"https:\/\/factormystic.net\/blog\/project-euler-in-fsharp-problem-2","title":{"rendered":"Project Euler in F#: Problem 2"},"content":{"rendered":"

Problem 2<\/h2>\n

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:
\n1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
\nFind the sum of all the even-valued terms in the sequence which do not exceed four million.<\/p><\/blockquote>\n

The Thinking<\/h2>\n

The problem is similar to Problem 1<\/a>, but this time instead of a natural number sequence, we’re to use a fibbonacci sequence, evens only, less than 4 million.\u00a0Then, we’ll need to sum them up; that we did in Problem 1 with Seq.sum.\u00a0How can we generate the sequence? I’ll be taking a simple two-step approach. First, figure out a function to generate a fibbonacci sequence (up through 4,000,000), then take all the evens. We can Seq.sum that resulting sequence to find our answer.<\/p>\n

Generating a Fibonacci Sequence<\/h2>\n

Generating a fibbonacci sequence in F# is a textboook case, and so much so that it’s actually an example snippet for the built-in F# function we’re going to use to generate it: Seq.unfold.\u00a0Seq.unfold is a \u00a0function that returns a sequence, based on a function we provide.\u00a0It takes two parameters: a sequence element generator function, and the inital value to start with.
\n[sourcecode]Seq.unfold generator state[\/sourcecode]
\nThe generator function must be defined with a single input parameter (the “state value”), and returning an “option tuple of the next element in the sequence and the next state value” (from documentation<\/a>).<\/p>\n

A fibbonacci algorithm requires two inputs (the previous two digits), but we can only pass one parameter. Luckily in F# we have Tuples<\/a>. A tuple lets us package up several values into a single group, and is written with as a comma separated list inside parenthesis:
\n[sourcecode]let sometuple = (“this”, “is”, “a”, “single”, “tuple”)[\/sourcecode]
\nThe return value is also something new, using the built-in Option module<\/a>. We’ll be returning an Option, either Some or None. None is a signal to unfold that this is the end of sequence, and for all the rest of the return results, we need to return Some-thing (the next element of the sequence as well as the next state value in tuple form) as we learned above, from the documentation for unfold.<\/p>\n

This might seem like a lot to process all at once, but it ends up looking pretty simple when it’s all put together. The generator function for fibbonacci numbers less than 4m looks like this:
\n[sourcecode]let fibgen (x,y) = \/\/define a function ‘fibgen’ and pass in a single parameter, a tuple that represents the most recent two digits of the fibbonacci sequence so far
\nif(x < 4000000) then \/\/ define a cut-off threshold to keep the sequence from going on forever\nSome(x+y, (y, x+y)) \/\/ return an Option tuple; the next elemnet of the sequence: x+y (the two most recent elements added together), and the next state value- a single tuple that will be used next time the funciton is run\nelse None \/\/ we're up to 4m, so tell unfold we're done with the sequence\n[\/sourcecode]\n\nAnd now, we can plug that into Seq.unfold:\n[sourcecode]let fibseq = Seq.unfold fibgen (1,1) \/\/ (1,1) is a single tuple parameter with the initial values for the fibgen function[\/sourcecode]\n\nIf we run this in the Interactive F# window in Visual Studio, we can confirm this produces the full fibbonacci sequence:\n[sourcecode]val it : seq = seq [2; 3; 5; 8; ...][\/sourcecode]\n\n\n\n

Getting Just The Evens<\/h2>\n

If you recall our solution to Problem 1<\/a>, it should be easy to figure out how to make a new sequence with only the even values by using seq, modulo, and yield that we’ve already learned.
\n[sourcecode]let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i}[\/sourcecode]<\/p>\n

My Solution<\/h2>\n

Putting it all together, with Seq.sum to add up the sequence:
\n[sourcecode]let fibgen (x,y) = if(x < 4000000) then Some(x+y, (y, x+y)) else None\nlet fibseq = Seq.unfold fibgen (1,1)\nlet fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i}\nlet result = Seq.sum fibevens\nprintfn \"%A\" result\n[\/sourcecode]\n\nProject Euler Problem 2: Answered<\/a><\/strong><\/p>\n

Further Reading<\/h2>\n