Project Euler: Problem 25

This puzzle requires that we find the first Fibonacci number with 1000 digits.

Given what we have already created in problem 2 it is a fairly simple problem to solve. All we need to do is to introduce a new function that checks the digit count:

let hasYdigits x y =

    let upperLimit = BigInteger.Pow(10I,y-1)

    x >= upperLimit


let has1000digits (x : BigInteger) =  hasYdigits x 1000

Note that I'm being explicit about the type of the parameter because I want it to use BigIntegers.

Now the problem is solved by filtering out all elements in the infinite list that don't have 1000 digits and with the resulting sequence taking the first element (Seq.head) and then bailing out.

let euler25 = fibSet

                |> Seq.filter (fun x -> has1000digits x)

                |> Seq.head 


printfn "%A" euler25

Console.ReadLine() |> ignore


Project Euler: Problem 2

This problem requires that we calculate the sum of the all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Using F# this is a fairly simple problem to solve. We need 3 things:

  • A function that generates Fibonacci numbers
  • A function that determines if a number is even
  • A function that determines if a number is less than another number

Clearly the last 2 parts of this are fairly trivial. You could use anonymous functions (lambdas) but since I suspect I'll need these functions again in future I've defined them as named functions in their own right. In F#, the code for these 2 functions looks like this:

let isEven i = (i%2=0)


let isLessThan x y = x < y

Now for the Fibonacci number generator. From the definition of Fibonacci numbers it is fairly easy to come up with a recursive function as follows:

// simple form

let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)

Or if you prefer pattern matching syntax that better deals with boundary conditions, something like this might look better:

// using parameter matching

let rec fib n =

    match n with

    | n when n<1 -> failwith "Values must be greater than 0"

    | 1 -> 1

    | 2 -> 1

    | x -> fib x-2 + fib x-1

However, both of these functions suffer from performance problems because they repeatedly calculate the same Fibonacci numbers. The answer to this problem is, of course, memoization. Adding this the code would like a little better:

// adding memoization

let fibNumbers = new Dictionary<int,int>()

fibNumbers.[1] <- 1

fibNumbers.[2] <- 1


let rec fib n =

     if n<1 then failwith "Values must be greater than 0" else

         if fibNumbers.ContainsKey(n) then fibNumbers.[n] else

            let result = fib (n-1) + fib (n-2)

            fibNumbers.[n] <- result


but there is also another issue to consider. We do not know how many numbers we will need. In this situation it's best to use a sequence rather than a finite list. A sequence is a logical series of elements all of one type. Individual sequence elements are computed only as required (lazy evaluation), so a sequence can provide performance improvements compared to a list in situations where not all the elements are used, and a sequence can produce an infinite list.

// making an infinite list (sequence)

let fibSet =

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

Here, Seq.unfold generates a sequence from a computation function that takes a state and transforms it to produce each subsequent element in the sequence. Because each element in the Fibonacci sequence is the sum of the previous two Fibonacci numbers, the state value is a tuple that consists of the previous two numbers in the sequence. The initial value is (1,1), the first two numbers in the sequence. The I suffix is used to denote a BigInteger type.

We can now compose all these functions to solve the problem. We simply iterate over the sequence (infinite list) until we reach our termination criteria (the Fibonacci number exceeds 4 million), summing the numbers as we go.

// making an infinite list (sequence)

let fibSet =

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


// use this if you want to print out the first c numbers in the sequence

let printfibNumberSet c =

    for x in 1..c do

        printf "%A," (fib x)


// utility functions

let isEven i = (i%2I=0I)


let isLessThan x y = x < y


// making an infinite list (sequence)

let euler2 = fibSet

                |> Seq.takeWhile (fun x -> (isLessThan x 4000000I))

                |> Seq.filter (fun x -> isEven x)

                |> Seq.sum


printfn "%A" euler2

Console.ReadLine() |> ignore

One final note...there is a closed-form solution to calculating the n-th Fibonacci number.

It's called Binet's formula and it can be formulated as follows in F#:

let phi = (1.0 + sqrt 5.0)/2.0

let fibN n = Math.Round((phi**n - (1.0 - phi)**n)/(sqrt 5.0) , MidpointRounding.AwayFromZero )

If you don't want a recursive formula you can use this approach.



Stepping Stones Puzzle

Questions: Given that you can take 1 or 2 steps forward from a given step, what is the total number of ways of reaching the Nth step?

Solution: Firstly, let us consider an arbitrary step, i. This step can be reached by:

  1. being on the (i-1)-th step and advancing forward 1 step, OR
  2. being on the (i-2)-th step and advancing forward 2 steps.

If we let f be a function which defines the total number of ways of reaching a given step, we can mathematically express the scenario described above as follows:

In other words, the total number of ways of reaching step i is a function of the total number of ways you can reach each of the 2 previous steps. This is, of course, a recurrence relationship describing the Fibonacci-like sequence. By their nature, recurrence relationships are amenable to recursive solutions - although it is often more efficient to find a closed-form solution! To solve the above equation recursively one only needs to know the seed values f(1) and f(2). In this case, f(0) is not required, f(1)=1 and f(2) = 2 and for n>2 the above formula can be used. QED