Question
I'm a bit stuck on the last step of getting the solution to problem 2 on Project Euler. This is the source I've gotten so far.
#light
module pe2 (* Project Euler Problem 2 solution *)
open System
let Phi = 1.6180339887;;
let invPhi = 1.0/Phi;;
let rootOfFive = 2.236067977;;
let maxFib = 4000000.0;
let Fib n =
System.Math.Round((Phi**n - invPhi**n)/rootOfFive);;
let FibIndices = Seq.unfold(fun i -> Some(i, i+3.0)) 3.0;;
let FibNos = FibIndices |> Seq.map(fun index -> Fib(index));;
let setAllowedFibNos = FibNos |> Seq.filter(fun fn -> (fn <= maxFib));;
// let answer = setAllowedFibNos |> Seq.fold (+) 0.0;
When I uncomment the last line, the process never seems to finish. So I was hoping that someone could give me a gentle nudge in the right direction. I did look at setAllowedFibNos and it looks right but it's also an infinite sequence so I only see the first three terms.
Also, could someone point me to the right way to chain the various sequences together? I tried something like this:
let answer = Seq.unfold(fun i-> Some(i, i + 3.0)) 3.0
|> Seq.map (fun index -> Fib(index))
|> Seq.filter(fun fn -> (fn <= maxFib))
|> Seq.fold (+) 0.0;;
But that didn't work. As you can probably guess I'm just learning F# so please go gentle and if this sort of question has been asked and answered before, please post a link to the answer and I'll withdraw this one.
Solution
'setAllowedFibNos' is indeed an infinite seq computation; 'fold' needs the whole sequence, so the 'filter' will run forever looking for another number <= maxFib.
Take a look at takeWhile:
I think it is what you want instead of filter.
Also note that you can use 'sqrt 5.0'.
OTHER TIPS
let rec Fib(n) =
if (n < 2) then
1
else
Fib(n-2) + Fib(n-1)
Seq.initInfinite Fib
|> Seq.takeWhile (fun a -> a <= 4000000)
|> Seq.filter (fun a -> (a % 2) = 0)
|> Seq.fold (+) 0
I'm still trying to get used to the Seq approach. But, here is my solution without it.
#light
let rec fib n =
match n with
|0|1 -> n
|_ -> fib(n-1) + fib(n-2)
let maxFib = 4000000
let phi = (1.0 + sqrt(5.0)) / 2.0
let upperBound = 1 + int( log10((float(maxFib) - 0.5) * sqrt(5.0)) / log10(phi))
[1..upperBound] |> List.filter (fun x-> x%3=0) |> List.map fib |> List.filter (fun x -> x%2 = 0) |> List.filter (fun x -> x List.sum |> printfn "%d"
My solution is:
Seq.unfold (fun state ->
if (fst state + snd state > 4000000) then None
else Some(fst state + snd state, (snd state, fst state + snd state))) (0,1)
|> Seq.filter (fun x -> x % 2 = 0)
|> Seq.sum;;