Geeks With Blogs
Buhay Programmer Dont byte more than you can chew

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

# re: F# Solution : Project Euler Problem 25
Requesting Gravatar...
Nice!

Can you replace two lines with something like:

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

instead?
Left by Jon Harrop on Jan 20, 2008 7:26 AM

# re: F# Solution : Project Euler Problem 25
Requesting Gravatar...
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
Left by Chance on Jan 20, 2008 11:06 PM

# re: F# Solution : Project Euler Problem 25
Requesting Gravatar...
Dr Jon,

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!

Left by Erik on Jan 21, 2008 12:24 PM

# re: F# Solution : Project Euler Problem 25
Requesting Gravatar...
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.

let euler25 = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0 + n1))) (0I,1I) |> Seq.takeWhile ((>) (pown 10I 999)) |> Seq.length;;
Left by Joel Mueller on Feb 23, 2010 4:17 PM

Your comment:
 (will show your gravatar)


Copyright © Erik Araojo | Powered by: GeeksWithBlogs.net