Skip to content

Fibonacci Sequence

The Fibonacci sequence (OEIS A000045) is defined as follows:

\[ F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} \]

The first few terms of the sequence are:

\[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots \]

Lucas Sequence

The Lucas sequence (OEIS A000032) is defined as follows:

\[ L_0 = 2, L_1 = 1, L_n = L_{n-1} + L_{n-2} \]

The first few terms of the sequence are:

\[ 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, \dots \]

Studying the Fibonacci sequence often requires using the Lucas sequence as a tool.

Closed-form Expression for Fibonacci Numbers

The \(n\)-th Fibonacci number can be computed in \(\Theta (n)\) time using the recurrence relation. However, there are faster methods.

Closed-form Solution

The closed-form solution is given by Binet's Formula:

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

This formula can be easily proven by induction, derived using generating functions, or obtained by solving an equation.

You may notice that the second term in the numerator is always less than \(1\) and decreases exponentially. Therefore, the formula can be written as:

\[ F_n = \left[\frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n}{\sqrt{5}}\right] \]

Here, the brackets denote rounding to the nearest integer.

Both formulas require extremely high precision in computation, so they are rarely used in practice. However, do not overlook them! Combined with the concepts of quadratic residues and modular inverses, this formula can still be useful in OI.

Closed-form Expression for Lucas Numbers

We have the closed-form formula for Lucas numbers:

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

This is very similar to the Fibonacci sequence. In fact:

\[ \frac{L_n + F_n\sqrt{5}}{2} = \left(\frac{1 + \sqrt{5}}{2}\right)^n \]

That is, \(L_n\) and \(F_n\) exactly correspond to the coefficients of the binomial expansion of \(\left(\frac{1 + \sqrt{5}}{2}\right)^n\) after combining like terms. In other words, all solutions to the Pell equation

\[ x^2-5y^2=-4 \]

are exactly

\[ \frac{x_n + y_n\sqrt{5}}{2} = \frac{L_n + F_n\sqrt{5}}{2} \]

which are precisely the Lucas and Fibonacci sequences. Therefore:

\[ {L_n}^2-5{F_n}^2=-4 \]

Matrix Form

The recurrence of the Fibonacci sequence can be expressed in matrix multiplication form:

\[ \begin{bmatrix}F_{n-1} & F_{n} \cr\end{bmatrix} = \begin{bmatrix}F_{n-2} & F_{n-1} \cr\end{bmatrix} \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix} \]

Let \(P = \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix}\). Then we have:

\[ \begin{bmatrix}F_n & F_{n+1} \cr\end{bmatrix} = \begin{bmatrix}F_0 & F_1 \cr\end{bmatrix} P^n \]

Thus, we can compute the Fibonacci sequence in \(\Theta(\log n)\) time using matrix exponentiation. Additionally, the formulas discussed in the previous section can also be derived using matrix diagonalization techniques.

Fast Doubling Method

Using the above method, we can derive the following identities:

\[ \begin{aligned} F_{2k} &= F_k (2 F_{k+1} - F_{k}) \\ F_{2k+1} &= F_{k+1}^2 + F_{k}^2 \end{aligned} \]

Thus, we can quickly compute two adjacent Fibonacci numbers using this method (with a smaller constant than matrix exponentiation). The code below returns a pair \((F_n,F_{n+1})\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pair<int, int> fib(int n) {
  if (n == 0) return {0, 1};
  auto p = fib(n >> 1);
  int c = p.first * (2 * p.second - p.first);
  int d = p.first * p.first + p.second * p.second;
  if (n & 1)
    return {d, c + d};
  else
    return {c, d};
}

Properties

The Fibonacci sequence has many interesting properties. Here are some simple ones:

  1. Cassini's identity: \(F_{n-1} F_{n+1} - F_n^2 = (-1)^n\).
  2. Addition property: \(F_{n+k} = F_k F_{n+1} + F_{k-1} F_n\).
  3. Setting \(k = n\) in the above property, we get \(F_{2n} = F_n (F_{n+1} + F_{n-1})\).
  4. From the above property, it can be proven by induction that \(\forall k\in \mathbb{N},F_n|F_{nk}\).
  5. The above property is reversible: \(\forall F_a|F_b,a|b\).
  6. GCD property: \((F_m, F_n) = F_{(m, n)}\).
  7. Using two consecutive Fibonacci numbers as input to the Euclidean algorithm achieves the worst-case complexity (see Wikipedia - Gabriel Lamé).

Relationship Between Fibonacci and Lucas Sequences

It is not difficult to see that the equations relating Lucas and Fibonacci numbers bear a strong resemblance to trigonometric identities. For example:

\[ \frac{L_n + F_n\sqrt{5}}{2} = \left(\frac{1 + \sqrt{5}}{2}\right)^n \]

resembles

\[ \cos nx + i\sin nx = \left(\cos x + i\sin x\right)^n \]

and

\[ {L_n}^2-5{F_n}^2=-4 \]

resembles

\[ \cos^2 x + \sin^2 x = 1 \]

Thus, the Lucas sequence resembles the cosine function, while the Fibonacci sequence resembles the sine function. For instance, from

\[ \left(\frac{1 + \sqrt{5}}{2}\right)^m\left(\frac{1 + \sqrt{5}}{2}\right)^n = \left(\frac{1 + \sqrt{5}}{2}\right)^{m+n} \]

we can derive identities for the sum of indices:

\[ 2L_{m+n}=5F_mF_n+L_mL_n \]
\[ 2F_{m+n}=F_mL_n+L_mF_n \]

From this, we can deduce identities for doubling the index:

\[ L_{2n}={L_n}^2-2{\left(-1\right)}^n \]
\[ F_{2n}=F_nL_n \]

This is also a method for fast doubling of indices. Similarly, by imitating trigonometric formulas such as parity, sum-to-product, product-to-sum, half-angle, and universal substitution, we can derive more corresponding equations for Lucas and Fibonacci sequences.

Fibonacci Coding

We can use the Fibonacci sequence to encode positive integers. According to Zeckendorf's theorem, any natural number \(n\) can be uniquely expressed as a sum of distinct Fibonacci numbers:

\[ N = F_{k_1} + F_{k_2} + \ldots + F_{k_r} \]

with \(k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\ \ldots,\ k_r \ge 2\) (i.e., no two consecutive Fibonacci numbers are used).

Thus, we can represent a positive integer using the encoding \(d_0 d_1 d_2 \dots d_s 1\), where \(d_i=1\) indicates that \(F_{i+2}\) is used. We forcibly append a \(1\) at the end of the encoding (which will create two adjacent \(1\)s) to indicate the end of the encoding. Here are some examples:

\[ \begin{aligned} 1 &=& 1 &=& F_2 &=& (11)_F \\ 2 &=& 2 &=& F_3 &=& (011)_F \\ 6 &=& 5 + 1 &=& F_5 + F_2 &=& (10011)_F \\ 8 &=& 8 &=& F_6 &=& (000011)_F \\ 9 &=& 8 + 1 &=& F_6 + F_2 &=& (100011)_F \\ 19 &=& 13 + 5 + 1 &=& F_7 + F_5 + F_2 &=& (1001011)_F \end{aligned} \]

The encoding process for \(n\) can be solved using a greedy algorithm:

  1. Enumerate Fibonacci numbers \(F_i\) from largest to smallest until \(F_i\le n\).
  2. Subtract \(F_i\) from \(n\), and place a \(1\) at position \(i-2\) in the encoding (positions are indexed from left to right starting at \(0\)).
  3. If \(n\) is positive, return to step 1.
  4. Finally, append a \(1\) to the end of the encoding to indicate the end.

The decoding process is similar: first remove the trailing \(1\), then for each position \(i\) (indexed from left to right starting at \(0\)) where the encoding is \(1\), add \(F_{i+2}\) to the answer. The final sum is the original number.

Periodicity Under Modulo

Consider the Fibonacci sequence modulo \(p\). Using the pigeonhole principle, it can be easily shown that the sequence is periodic. Consider the first \(p^2+1\) pairs of consecutive Fibonacci numbers modulo \(p\):

\[ (F_1,\ F_2),\ (F_2,\ F_3),\ \ldots,\ (F_{p^2 + 1},\ F_{p^2 + 2}) \]

The residue system modulo \(p\) has size \(p\), so among the first \(p^2+1\) pairs, there must be two identical pairs. These two pairs will generate the same Fibonacci sequence thereafter, indicating periodicity.

Pisano Period

The smallest positive period of the Fibonacci sequence modulo \(m\) is called the Pisano period (OEIS A001175).

The Pisano period never exceeds \(6m\), and equality holds only when \(m=2\times 5^k\).

When computing the \(n\)-th Fibonacci number modulo \(m\) for very large \(n\), it is necessary to compute the period of the Fibonacci sequence modulo \(m\). Note that we only need to compute a period, not necessarily the minimal positive period.

It is easy to verify that the minimal positive period of Fibonacci numbers modulo \(2\) is \(3\), and modulo \(5\) is \(20\).

Clearly, if \(a\) and \(b\) are coprime, the Pisano period of \(ab\) is the least common multiple of the Pisano periods of \(a\) and \(b\).

Computing the period also requires the following conclusions:

Conclusion 1: For odd primes \(p\equiv 1,4 \pmod 5\), \(p-1\) is a period of Fibonacci numbers modulo \(p\). That is, the Pisano period of an odd prime \(p\) divides \(p-1\).

Proof:

In this case, \(5^\frac{p-1}{2} \equiv 1\pmod p\).

By binomial expansion:

\[ F_p=\frac{2}{2^p\sqrt{5}}\left(\dbinom{p}{1}\sqrt{5}+\dbinom{p}{3}\sqrt{5}^3+\ldots+\dbinom{p}{p}\sqrt{5}^p\right)\equiv\sqrt{5}^{p-1}\equiv 1\pmod p \]
\[ F_{p+1}=\frac{2}{2^{p+1}\sqrt{5}}\left(\dbinom{p+1}{1}\sqrt{5}+\dbinom{p+1}{3}\sqrt{5}^3+\ldots+\dbinom{p+1}{p}\sqrt{5}^p\right)\equiv\frac{1}{2}\left(1+\sqrt{5}^{p-1}\right)\equiv 1\pmod p \]

Since both \(F_p\) and \(F_{p+1}\) are congruent to \(1\), matching \(F_1\) and \(F_2\), \(p-1\) is a period.

Conclusion 2: For odd primes \(p\equiv 2,3 \pmod 5\), \(2p+2\) is a period of Fibonacci numbers modulo \(p\). That is, the Pisano period of an odd prime \(p\) divides \(2p+2\).

Proof:

In this case, \(5^\frac{p-1}{2} \equiv -1\pmod p\).

By binomial expansion:

\[ F_{2p}=\frac{2}{2^{2p}\sqrt{5}}\left(\dbinom{2p}{1}\sqrt{5}+\dbinom{2p}{3}\sqrt{5}^3+\ldots+\dbinom{2p}{2p-1}\sqrt{5}^{2p-1}\right) \]
\[ F_{2p+1}=\frac{2}{2^{2p+1}\sqrt{5}}\left(\dbinom{2p+1}{1}\sqrt{5}+\dbinom{2p+1}{3}\sqrt{5}^3+\ldots+\dbinom{2p+1}{2p+1}\sqrt{5}^{2p+1}\right) \]

After modulo \(p\), in \(F_{2p}\), only the term \(\dbinom{2p}{p}\equiv 2 \pmod p\) remains; in \(F_{2p+1}\), the terms \(\dbinom{2p+1}{1}\equiv 1 \pmod p\), \(\dbinom{2p+1}{p}\equiv 2 \pmod p\), and \(\dbinom{2p+1}{2p+1}\equiv 1 \pmod p\) remain.

\[ F_{2p}\equiv\frac{1}{2}\dbinom{2p}{p}\sqrt{5}^{p-1}\equiv -1 \pmod p \]
\[ F_{2p+1}\equiv\frac{1}{4}\left(\dbinom{2p+1}{1}+\dbinom{2p+1}{p}\sqrt{5}^{p-1}+\dbinom{2p+1}{2p+1}\sqrt{5}^{2p}\right)\equiv\frac{1}{4}\left(1-2+5\right)\equiv 1 \pmod p \]

Thus, \(F_{2p}\) and \(F_{2p+1}\) match \(F_{-2}\) and \(F_{-1}\), so \(2p+2\) is a period.

Conclusion 3: For a prime \(p\), if \(M\) is a period of Fibonacci numbers modulo \(p^{k-1}\), then \(Mp\) is a period of Fibonacci numbers modulo \(p^k\). In particular, if \(M\) is the Pisano period modulo \(p^{k-1}\), then \(Mp\) is the Pisano period modulo \(p^k\).

Proof:

This proof treats \(\frac{1+\sqrt{5}}{2}\) as a whole.

Since:

\[ F_M=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^M-\left(\frac{1-\sqrt{5}}{2}\right)^M\right)\equiv 0\pmod {p^{k-1}} \]
\[ F_{M+1}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{M+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{M+1}\right)\equiv 1\pmod {p^{k-1}} \]

Therefore:

\[ \left(\frac{1+\sqrt{5}}{2}\right)^M \equiv \left(\frac{1-\sqrt{5}}{2}\right)^M\pmod {p^{k-1}} \]
\[ 1\equiv\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^M\left(\left(\frac{1+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)\right)=\left(\frac{1+\sqrt{5}}{2}\right)^M\pmod {p^{k-1}} \]

Since the converse can also be derived, \(M\) is a period of Fibonacci numbers modulo \(p^{k-1}\) if and only if:

\[ \left(\frac{1+\sqrt{5}}{2}\right)^M \equiv \left(\frac{1-\sqrt{5}}{2}\right)^M\equiv 1\pmod {p^{k-1}} \]

When \(p\) is an odd prime, by the Lifting the Exponent Lemma, we have:

\[ \nu_p\left(a^t-1\right)=\nu_p\left(a-1\right)+\nu_p(t) \]

When \(p=2\), by the Lifting the Exponent Lemma, we have:

\[ \nu_2\left(a^t-1\right)=\nu_2\left(a-1\right)+\nu_2\left(a+1\right)+\nu_2(t)-1 \]

Substituting \(a\) with \(\left(\frac{1+\sqrt{5}}{2}\right)\) and \(\left(\frac{1-\sqrt{5}}{2}\right)\), and \(t\) with \(M\) and \(Mp\), the above condition is equivalent to:

\[ \left(\frac{1+\sqrt{5}}{2}\right)^{Mp} \equiv \left(\frac{1-\sqrt{5}}{2}\right)^{Mp}\equiv 1\pmod {p^k} \]

Thus, it is also equivalent to \(Mp\) being a period of Fibonacci numbers modulo \(p^k\).

Since the periods are equivalent, the minimal positive periods are also equivalent.

With these three conclusions proven, we can write the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct prime {
  unsigned long long p;
  int times;
};

struct prime pp[2048];
int pptop;

unsigned long long get_cycle_from_mod(
    unsigned long long mod)  // This only computes a period, not necessarily the minimal positive period.
{
  pptop = 0;
  srand(time(nullptr));
  while (n != 1) {
    __int128_t factor = (__int128_t)10000000000 * 10000000000;
    min_factor(mod, &factor);  // Compute the smallest prime factor
    struct prime temp;
    temp.p = factor;
    for (temp.times = 0; mod % factor == 0; temp.times++) {
      mod /= factor;
    }
    pp[pptop] = temp;
    pptop++;
  }
  unsigned long long m = 1;
  for (int i = 0; i < pptop; ++i) {
    int g;
    if (pp[i].p == 2) {
      g = 3;
    } else if (pp[i].p == 5) {
      g = 20;
    } else if (pp[i].p % 5 == 1 || pp[i].p % 5 == 4) {
      g = pp[i].p - 1;
    } else {
      g = (pp[i].p + 1) << 1;
    }
    m = lcm(m, g * qpow(pp[i].p, pp[i].times - 1));
  }
  return m;
}

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用