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.
As discussed in prob. 2, the closed form $i^{\text{th}}$ Fibonacci number is:
$$F_{i} = \frac{(\frac{1+\sqrt{5}}{2})^{i} - (\frac{1-\sqrt{5}}{2})^{i}}{\sqrt{5}}$$The number of digits is given by: $$\lceil log_{10} F_{i} \rceil = \lceil log_{10} \frac{(\frac{1+\sqrt{5}}{2})^{i} - (\frac{1-\sqrt{5}}{2})^{i}}{\sqrt{5}}\rceil$$
and since $(\frac{1-\sqrt{5}}{2})^{i} \rightarrow 0$ as $i \rightarrow \infty$, we have: $$\lceil log_{10} F_{i} \rceil \approx \lceil i log_{10} \frac{1-\sqrt{5}}{2} - \frac{1}{2} log_{10}(5) \rceil$$
In [1]:
import math
(999 + 0.5*math.log(5)/math.log(10)) / (math.log(((1+5**.5)/2))/math.log(10))
Out[1]:
In [2]:
math.ceil(4782 * math.log(((1+5**.5)/2))/math.log(10) - 0.5*math.log(5)/math.log(10))
Out[2]: