## Project Euler in F#: Problem 2

## Problem 2

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

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

## The Thinking

The problem is similar to Problem 1, but this time instead of a natural number sequence, we're to use a fibbonacci sequence, evens only, less than 4 million. Then, we'll need to sum them up; that we did in Problem 1 with Seq.sum. How 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.

## Generating a Fibonacci Sequence

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. Seq.unfold is a function that returns a sequence, based on a function we provide. It takes two parameters: a sequence element generator function, and the inital value to start with.

Seq.unfold generator state

The 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 fibbonacci algorithm requires two inputs (the previous two digits), but we can only pass one parameter. Luckily in F# we have Tuples. A tuple lets us package up several values into a single group, and is written with as a comma separated list inside parenthesis:

let sometuple = ("this", "is", "a", "single", "tuple")

The return value is also something new, using the built-in Option module. 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.

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:

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 if(x < 4000000) then // define a cut-off threshold to keep the sequence from going on forever Some(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 else None // we're up to 4m, so tell unfold we're done with the sequence

And now, we can plug that into Seq.unfold:

let fibseq = Seq.unfold fibgen (1,1) // (1,1) is a single tuple parameter with the initial values for the fibgen function

If we run this in the Interactive F# window in Visual Studio, we can confirm this produces the full fibbonacci sequence:

val it : seq = seq [2; 3; 5; 8; ...]

## Getting Just The Evens

If you recall our solution to Problem 1, 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.

let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i}

## My Solution

Putting it all together, with Seq.sum to add up the sequence:

let fibgen (x,y) = if(x < 4000000) then Some(x+y, (y, x+y)) else None let fibseq = Seq.unfold fibgen (1,1) let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i} let result = Seq.sum fibevens printfn "%A" result

Project Euler Problem 2: **Answered**

## Further Reading

- Chapter 8- Functions & Functional Concepts, The F# Survival Guide
- Mark Pearl's post on Seq.Unfold, using tuple parameters and pipelines
- Seq.unfold
- Options module
- Tuples

## A Post Script

Each part of the above solution is named for clarity. We could easily compose these functions for a more compact solution:

printfn "%A" (Seq.sum(seq{for i in ((1,1) |> Seq.unfold(fun (x,y) -> if(x < 4000000) then Some(x+y, (y, x+y)) else None)) do if i % 2 = 0 then yield i}))

The only thing that gets weird in this compact version is the anonymous replacement for fibgen, which uses lambda syntax fun & ->, and the pipeline operator, |> to pass in the intial state. There are some goofy rules for when you can and cannot use piplineing; check out the Pipeline section of Chapter 8 of The F# Survival Guide for a good primer.

## Project Euler in F#: Problem 1

## About Project Euler

I've wanted to take a crack at Project Euler for some time now. If you're not familiar, it's basically a list of mathematical problems. From the site:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

And they keep score! In addition, I've also been looking for an excuse to learn F#. In truth, I've wanted to get down and dirty with some functional language, to learn the principles and hopefully become a better programmer. I chose F# because it's part of Visual Studio (starting with 2010), and I'm already handy with .NET, so in theory that will lower the barrier to entry just a little bit. At the very least, it allows me to dodge the hassle of installing another interpreter or environment on my system.

## Blogging It

As I continue though Project Euler, I'll be posting my solutions here on my site under http://factormystic.net/projects/code, and you can also check my progress by looking at my Project Euler profile and I look forward to your mocking laughter gentle guidance as I fumble around in F#.

## On to Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Straightforward enough, and easy to form a mental model around the problem. But how to implement this in F#? For a quick language primer, I skimmed An Introduction to Functional Programming for .NET Developers and noticed a few things I might need:

- An add function

let add x y = x + y

- Sequence syntax and list comprehension

let numbers = {0..10}

- Modulo and ternary operators

string result = x % 2 == 0 ? "yes" : "no";

## The Thinking

The thinking is this: sequences could be used to build a list of integers 1 to 1000; I could use modulo to get multiples of 3 and 5 (think FizzBuzz), and somehow use that add function to get the sum. Reading the documentation for sequence expressions turned out to be quite rewarding (!), as you can embed a filter on a sequence when you declare it:

let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }

Yield is already a familiar concept from C#, from using Enumerables. In fact, from the documentation:

Sequences are represented by the seq<'T> type, which is an alias for IEnumerable<T>. Therefore, any .NET Framework type that implements System.IEnumerable can be used as a sequence. The Seq module provides support for manipulations involving sequences.

Thus our F# is roughly analogous to something like

public static IEnumerable GiveMults() { foreach (int i in Enumerable.Range(1, 1000)) if (i % 3 == 0 || i % 5 == 0) yield return i; }

Now that we have our sequence of natural numbers, let's figure out how to sum them up. I have the add function I grabbed from the article, and while poking around with the Seq module, I noticed a reduce function, which can apply an accumulator. That would give us

let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i } let add x y = x + y let result= Seq.reduce add multiples printfn "%A" result

(Side note: printfn is how we can write to stdout, much like Console.Writeline. The "%A" stuff works like string.Format parameters- %A indicates "Formats any value, printed with the default layout settings." In the case of a sequence, that means printing the first few values)

...and that code does indeed sum the multiples, as you would expect. But there is a better way. After all, we should expect something as simple as adding up a list to be built in already, and we do have our Seq module functions available.

Indeed, there is a Seq.sum function that does exactly what we're seeking to do, sum a sequence. Rewritten, we have:

let result = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i } let total = Seq.sum result printfn "%A" total

And this prints an answer, but that answer is WRONG. See the bug? The original problem stated that we're to "sum of all the multiples of 3 or 5 **below** 1000", but the list comprehension syntax (1..1000) is **inclusive**. Thus, our answer includes 1000, which is evenly divisible by 5, and is summed into the final total. The fix is simple, just write 1..999:

## My Solution

let multiples = seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i } let result = Seq.sum multiples printfn "%A" result

Bingo.

Project Euler Problem 1: **Answered**

## Further Reading

## A Post Script

For the code golf crew:

printfn "%A" (Seq.sum (seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }))