问题
斐波拉契序列是以循环的关系定义的：
\(F_n = F_{n-1} + F_{n-2}, 而 F_1 = 1, F_2 = 1\)因此，序列的头12个数字为：
\(F_1 = 1\)
\(F_2 = 1\)
\(F_3 = 2\)
\(F_4 = 3\)
\(F_5 = 5\)
\(F_6 = 8\)
\(F_7 = 13\)
\(F_8 = 21\)
\(F_9 = 34\)
\(F_{10} = 55\)
\(F_{11} = 89\)
\(F_{12} = 144\)
而第12项\(F_{12}\)，则是序列中的第一个三位数。
那请问斐波拉契序列中的第一个千位数字是第几项？
* 传送门
分析
又是斐波拉契序列。
用暴力方法解这个问题是可行的，前提是要使用BigInteger以免溢出，因为一千位的整数肯定会超出原生数据范围。
其实这个问题还可以直接用数学分析的方法求解，不需要写程序。前面已经在《Fibonacci通项公式推导》一文中推导通项公式，所以这里先直接列出通项公式：
\(F_n = \frac{1}{\sqrt{5}} \cdot [(\frac{1 + \sqrt{5}}{2})^n – (\frac{1 – \sqrt{5}}{2})^n]\)先观察括号中左右两项，\(\frac{1 + \sqrt{5}}{2} = 1.618033988749895…, \frac{1 – \sqrt{5}}{2} = -0.6180339887498949…\)。右边一项由于绝对值小于1，在n次方的运算后，随着n越大，右边一项会越来越接近0。换句话说，该通项公式随着n越大，左边一项的值便会越来越主导该公式的值，\(\frac{F_{n+1}}{F_n}\)的比值会越来越接近\(\frac{1 + \sqrt{5}}{2}\)。由于本问题目标项已经达到千位，所以这个趋势十分明显，该通项公式可以近似地只看左边一项。当\(F_n \approx \frac{1}{\sqrt{5}} \cdot (\frac{1 + \sqrt{5}}{2})^n < 10^{999}, F_{n+1} \approx \frac{1}{\sqrt{5}} \cdot (\frac{1 + \sqrt{5}}{2})^{n+1} \geq 10^{999}\)，n+1便是我们要找的序号。
实质上，就是要求解这个不等方程：\(10^{999} \cdot \frac{2\sqrt{5}}{1 + \sqrt{5}} \leq (\frac{1 + \sqrt{5}}{2})^n < 10^{999} \cdot \sqrt{5}\)
代入代数值，不等式则会变为\(1.381966011250105 \cdot 10^{999} \leq 1.618033988749895^n < 2.23606797749979 \cdot 10^{999}\)。咋看没法解，但实际上不是。中间一项，观察它的格式是否可以转换为\(1.618033988749895 \cdot 10^{x}\)这种形式。由于使用数学计算器便可得出\(\frac{1}{log(1.618033988749895)} \approx 4.785, 即 1.618033988749895^{4.785} \approx 10 \)，于是有：
\(\begin{aligned}1.618033988749895^n &= 1.618033988749895 \cdot 1.618033988749895^{n-1} \\
&= 1.618033988749895 \cdot (1.618033988749895^{4.785})^{\frac{n-1}{4.785}} \\
&\approx 1.618033988749895 \cdot 10^{\frac{n-1}{4.785}}
\end{aligned}\)
于是整个不等式又可以改写为：\(1.381966011250105 \cdot 10^{999} \leq 1.618033988749895 \cdot 10^{\frac{n-1}{4.785}} < 2.23606797749979 \cdot 10^{999}\)
在形式统一后，只需要大胆假设\(\frac{n-1}{4.785} = 999\)，便有\(n = \lfloor 999 \times 4.785 + 1 \rfloor = 4781\)。
所以，第一个千位数的序号是4782。
为什么这个大胆的假设可以成立？
在前面已经提及，由于斐波拉契数列随着n越来越大，相邻两项之间的比值越来越接近\(\frac{1 + \sqrt{5}}{2}\)，而不等式的上下界之比值又刚刚好是这个值，所以在这个区间范围内n有效的值肯定只有一个，而且当系数能满足不等式的情况下，级数必然相等。
答案
// answer: brute force
const start = Date.now()
const one = bigInt(1)
function* fib() {
let prev = one, curr = one
yield prev
while (true) {
const _curr_ = curr
yield _curr_
curr = prev.add(curr)
prev = _curr_
}
}
const one_K_digit_num = bigInt('1e999')
let result = 1
for (const F_n of fib()) {
if (F_n.geq(one_K_digit_num))
break
result++
}
alert(result + ', ' + (Date.now() - start) + 'ms')
