HOME SUMMARY

Problem 25

1. Problem

1000-digit Fibonacci Number

The Fibonacci sequence is defined by the recurrence relation:

\(F_n = F_{n-1} + F_{n-2}\), where \(F_1 = 1\) and \(F_2 = 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, \(F_{12}\), is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

1000位斐波那契数

斐波那契数列是按如下递归定义的数列:

\(F_n = F_{n-1} + F_{n-2}\), 其中 \(F_1 = 1\), \(F_2 = 1\).

在斐波那契数列中,第一个包含三位数字的是第 12 项。

在斐波那契数列中,第一个包含 1000 位数字的是第几项?

2. Solution

对于支持大数运算的 Elisp 来说,我们只需找到第一个大于 (expt 10 999) 的数字的序号即可:

(let ((index 2)
      (a 1)
      (b 1)
      (bound (expt 10 999)))
  (while (< b bound)
    (cl-psetq a b
              b (+ a b))
    (cl-incf index))
  index)

当然,如果你知道斐波那契数列的通项公式的话,也可以这样解:

\[Fib(n) = \frac{1}{\sqrt{5}}[(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n]\]

当 n 非常大时,上面公式的后一项可以忽略,从而只需要解以下不等式即可:

\[1.618...^n \le \sqrt{5} \cdot 10^{999}\]

两边取常用对数,有:

\[n \cdot lg(1.618...) \le 0.5\cdot lg(5) + 999\]

使用如下代码易得结果:

(ceiling
 (/ (+ 999 (* 0.5 (log 5 10)))
    (log (/ (+ 1 (sqrt 5)) 2) 10)))