The Problem : What is the first term in the Fibonacci sequence to contain 1000 digits?

The sweet solution :

#light

open System

let fib =
(1I,1I) |> Seq.unfold ( fun (sqEntry, acc) -> Some (acc, (acc, acc + sqEntry)) )
|> Seq.filter (fun x -> x.ToString().Length = 1000)
|> Seq.nth 0

print_any fib
Console.ReadLine()

ahh... such power and elegance....

Let me breakdown the solution

(1I,1I) |> Seq.unfold ( fun (sqEntry, acc) -> Some (acc, (acc, acc + sqEntry)) )

This line creates an inifinite list of fibonacci numbers using Seq.unfold. Let me say that again, it creates a in INFINITE list. How is that possible, you'd ask ? The reason is that F# performs Lazy Evaluation. By that, I mean the program will perform only the computation it needs to do. So in our case, the program will actually compute only the parts of the list that it will need. Here we used Seq.unfold to perform the computation. The unfold function creates a list and uses an accumulator to maintain the state between computations. The accumulator in this case is the tuple that contains the last 2 entries of the sequence

Seq.filter( fun x -> x.ToString().Length = 1000

This line applies the filter function to the sequence. This function returns a subset of the original list that matches the condition. In this case, the resulting list will contain only those numbers that is made up 1000 digits.

Seq.nth 0

This line retrieves the nth element in the sequence. Since the problem ask for the 1st term, naturally we retrieved the 0th element.

And finally the construct that ties everything together and makes the code such a wonder to look at is the

|> (the Pass-forward operator)

As its name implies, it passes forward the argument behind it to the function in front of it. So the solution in essence means

Pass the tuple (1I, 1I) to Seq.Unfold, then pass the resulting infinite list to Seq.filter, then pass the filtered list to Seq.nth which finally retrieves the 1st element!

Posted on Friday, January 18, 2008 5:24 PM | Back to top

Comments on this post: F# Solution : Project Euler Problem 25

That's a very nice solution! Very concise. Thank you for posting it. One tricky point is that the lazy evaluation is specific to Seq. F# in general will evaluate eagerly. Regards, Chance

This version doesn't do any string conversion, and as a result is very fast - 0.013 seconds on my machine. Plus, it's technically a single line of code - although I would normally break it up into 4 or so for readability.

Can you replace two lines with something like:

|> Seq.find (fun x -> x.ToString().Length = 1000)

instead?

Regards,

Chance

Yes indeed!

Seq.filter (fun x -> x.ToString().Length = 1000) |> Seq.nth 0

is equivalent to

Seq.find (fun x -> x.ToString().Length = 1000)

because Seq.find returns the first element in the list. :) Thank you very much for pointing that out. Now the solution is even much better!

*In a different note: When I get my pay next month, I'll make sure to subscribe to the F# journal. Great work on that one!

let euler25 = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0 + n1))) (0I,1I) |> Seq.takeWhile ((>) (pown 10I 999)) |> Seq.length;;