Project Euler – Problem 25 Solution

Problem

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1

F2 = 1

F3 = 2

F4 = 3

F5 = 5

F6 = 8

F7 = 13

F8 = 21

F9 = 34

F10 = 55

F11 = 89

F12 = 144

The 12th term, F12, is the first term to contain three digits.

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

Solution

let fibonacciSeq =
    Seq.unfold (fun (current, next) -> Some(current, (next, current + next))) (0I, 1I)
    |> Seq.filter (fun f -> f > 0I)

let answer = (Seq.findIndex (fun f -> f.ToString().Length >= 1000) fibonacciSeq) + 1

In my solution here I first created a Fibonacci sequence which starts with 1, 1, … all the way to infinity, and the second expression gives us the answer to the problem by using Seq.findIndex to find the index (zero-based) of the first element which contains 1000 digits. The ‘+ 1’ at the end simply converts the zero-based index to the one-based index which the problem is asking for.

  • Nikolay Artamonov

    Instead of ineffective counting of length of every next Fibonacci number with String.Length property, you may compare every next number with number 10^999 (10 powered by 999). So you drop all Fibonacci numbers are strictly less than 10^999 (N < 10^999) and next number will be the answer.

  • Omu

    can’t resist the force

    let p25 =
    let rec loop i n1 n2 =
    match n2 with
    |n when n > 10I**999 -> (i, n2)
    |n -> loop (i+1I) n2 (n1+n2)
    loop 2I 1I 1I;

    runs instantly