F# Project Euler Problem 2

Solving second problem for Project Euler Problem 2 is an interesting one.

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.

Challenge here is to generate a fibonacci sequence, which is the fib(n-1) + fib(n-2) formula. This generates a evaluation tree during recursion and becomes quite large when generating a large N fibonacci value, and stackoverflow happens. To tackle this problem in a more efficient way, we shouldn’t generate the number for N re-cursing backwards, but generate the number from summation forwards.

Here’s my first F# solution I came up with.

let initiniteFib =
    let rec fib1 n1 n2 =
        seq {
            yield n1
            yield! fib1 n2 (n1+n2)
        }
    fib1 0I 1I

let answer = initiniteFib 
                |> Seq.takeWhile (fun x -> x < 4000000I)
                |> Seq.filter (fun x -> x % 2I = 0I)
                |> Seq.sum

Another way to solve the same problem, is using Seq.unfold.

let answer = Seq.unfold (fun (first, second) -> Some(second, (second, first+second))) (0I, 1I)
                |> Seq.takeWhile (fun x-> x < 4000000I)
                |> Seq.filter (fun x -> x % 2I = 0I)
                |> Seq.sum

If you have more interesting ways to solve this, please share.

F# Project Euler Problem 1

Recently I have started getting more exposure about F# at work. Another developer and myself managed woto build a scheduling service purely written in F#, and it was a very humbling experience.

I’ve gotten much more confidence now writing in F#, and starting to actually enjoy it more than C#. It’s a very different mindset and paradigm to write functionally.

We’ve also started a small community at work learning, sharing and practicing in F#. One of the interesting exercises is solving mathematical problems in F# from Project Euler.

Here’s my solution in solving 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.

let answer = seq {1..999}
|> Seq.filter (fun n -> n % 3 = 0 || n % 5 = 0)
|> Seq.sum

Simple enough 🙂