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?
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.
2 thoughts on “Project Euler – Problem 25 Solution”
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.
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;