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 index of the first term in the Fibonacci sequence to contain 1000 digits?
We can easily bruth force this. Well, it's what I solved this problem sort of. Essentially, we keep track of the number of digits in a array until we hit 1000 digits. There's nothing special here. Rather than calculating the number of digits from the beginning of the digit: (i.e, iteratively divide by 10, until we hit zero, anmd keep track of how many 10's we divided out). Instead of this method, we can keep track of my many digits were in Fib_(n-1) if we want to find Fib_n. It can either increase in digit by 1 or remain the same number of digit. So, all we have to track is this difference!
Answer: 4782
Runtime: 19 ms