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.
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;
runs instantly