フィボナッチ数の性質と計算方法 (2) リュカ数

フィボナッチ数,アルゴリズム,リュカ数

208

この連載について

フィボナッチ数、リュカ数、そしてそれらを一般化した数列の基本的な性質と、コンピューターにおける計算方法について記述します。

本文

今回は、フィボナッチ数と対で語られることの多いリュカ数 (Lucas numbers) を扱います。
さらに、初項 $a_{0}, a_{1}$ や添字 $n$ の拡張について考察します。

定義

リュカ数

漸化式
$a_{0} = 2, a_{1} = 1, a_{n + 2} - a_{n + 1} - a_{n} = 0 (n \geq 0)$
で定義される数列に現れる数をリュカ数 (Lucas number) と呼ぶ。

リュカ数の定義は、フィボナッチ数の初項 $a_{0}$ のみを変更したものです。

なお、添字 $n$ を負数まで拡張すると、この数列は
$\dots, 18, - 11, 7, - 4, 3, - 1, 2, 1, 3, 4, 7, 11, 18, \dots$
となります。

また、リュカ数列が別の意味を持つ用語として定義されていることから、リュカ数 (Lucas numbers; 複数形) が上記の数列を表すようです。
cf. Lucas sequence - Wikipedia

一般項

リュカ数の一般項を求めます。
証明方法はフィボナッチ数とほぼ同じのため省略します。

リュカ数の一般項

$a_{n} = α^{n} + β^{n} = α^{n} + (- α)^{- n}$
ただし、 $α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 - \sqrt{5}}{2} .$

$n$ 番目のフィボナッチ数およびリュカ数をそれぞれ $F_{n}, L_{n}$ とすると、
$lim_{n \to \infty} \frac{L_{n}}{F_{n}} = \sqrt{5}$
となります。
比がほぼ $\sqrt{5}$ になる整数の組を、規則的にいくらでも見つけられるというのは面白い現象です。

次に、初項を一般化してみます。

数列 $a_{n}$ を漸化式
$a_{n + 2} - a_{n + 1} - a_{n} = 0 (n \geq 0)$
で定義する。 $a_{0}, a_{1}$ は任意の実数とする。

この数列の一般項は、
$a_{n} = \frac{α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})}{α - β} = \frac{α^{n} (2 a_{1} - a_{0} + a_{0} \sqrt{5}) - β^{n} (2 a_{1} - a_{0} - a_{0} \sqrt{5})}{2 \sqrt{5}}$
ただし、 $α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 - \sqrt{5}}{2} .$

フィボナッチ数のときの解法と同様にして、
$\begin{array}{r} {\begin{cases} a_{n + 1} - α a_{n} = β^{n} (a_{1} - α a_{0}) \\ a_{n + 1} - β a_{n} = α^{n} (a_{1} - β a_{0}) \end{cases} \end{array}$
となることから得られる。

次に、添字 $n$ を負数まで拡張します。

公式 2 は、任意の整数 $n$ に対して成り立つ。

$a_{n} + a_{n + 1} - a_{n + 2} = 0 (n < 0)$
とし、 $a_{- 1}, a_{- 2}, a_{- 3}, \dots$ と順に値が定まっていくと考え、 $n \geq 0$ のときと同様の解法を用いる。

2 次方程式 $x^{2} + x - 1 = 0$ の 2 解は $x = - α, - β$ だから、 $n \leq 1$ に対し、
$a_{n} = \frac{(- α)^{1 - n} (a_{0} + β a_{1}) - (- β)^{1 - n} (a_{0} + α a_{1})}{- (α - β)} = \frac{(- α)^{- n} (a_{1} - α a_{0}) - (- β)^{- n} (a_{1} - β a_{0})}{- (α - β)} = \frac{α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})}{α - β}$
ここで、 $α β = - 1$ を使った。

ところで、フィボナッチ数やリュカ数では、 $a_{- n} = \pm a_{n}$ が成り立っていました。
このような性質を持つ数列はどれだけあるのでしょうか。

任意の整数 $n$ に対して、数列 $a_{n}$ を漸化式
$a_{n + 2} - a_{n + 1} - a_{n} = 0$
で定義する。 $a_{0}, a_{1}$ は任意の実数とする。

このとき、任意の整数 $n$ に対して $a_{- n} = (- 1)^{n + 1} a_{n}$ を満たす $a_{n}$ は、フィボナッチ数の定数倍に限られる。
また、任意の整数 $n$ に対して $a_{- n} = (- 1)^{n} a_{n}$ を満たす $a_{n}$ は、リュカ数の定数倍に限られる。

$α + β = 1, α β = - 1$ を用いる。

$a_{- n} = (- 1)^{n + 1} a_{n}$ を式変形していくと、
$α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = (- 1)^{n + 1} (α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})) α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = - β^{- n} (a_{1} - β a_{0}) + α^{- n} (a_{1} - α a_{0}) α^{- n} (α - β) a_{0} + β^{- n} (α - β) a_{0} = 0 (α^{- n} + β^{- n}) (α - β) a_{0} = 0$
したがって $a_{0} = 0$ となり、これはフィボナッチ数の定数倍を意味する。

また、 $a_{- n} = (- 1)^{n} a_{n}$ を式変形していくと、
$α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = (- 1)^{n} (α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})) α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = β^{- n} (a_{1} - β a_{0}) - α^{- n} (a_{1} - α a_{0}) α^{- n} (2 a_{1} - (α + β) a_{0}) - β^{- n} (2 a_{1} - (α + β) a_{0}) = 0 (α^{- n} - β^{- n}) (2 a_{1} - a_{0}) = 0$
したがって $a_{0} = 2 a_{1}$ となり、これはリュカ数の定数倍を意味する。

リュカ数の計算

リュカ数をコンピューターで具体的に求める方法をいくつか挙げます。
内容は前回のフィボナッチ数とほぼ同様で、とくに新しい説明はありません。一般項から求める方法は省略します。
以下、 $a_{0}, a_{1}$ は整数とし、 $n \geq 0$ とします。

漸化式から求める

リュカ数を整数のまま計算するには、定義の漸化式を用いて順に求めるのが簡単です。
時間計算量は $O (n)$ です。
空間計算量は、途中の値をキャッシュする場合は $O (n)$ 、キャッシュしない場合は $O (1)$ でできます。
任意の $a_{0}, a_{1}$ に対しても同様です。

C# では次のようなコードでリュカ数を作れます。
なお、 $a_{n}$ の値を符号付き 64 ビット整数で表せる範囲は $n \leq 90$ しかありません。

          public static long[] CreateSeq(int nLast = 90)
    {
        var a = new long[nLast + 1];
        a[0] = 2;
        a[1] = 1;
        for (int i = 2; i <= nLast; i++)
            a[i] = a[i - 1] + a[i - 2];
        return a;
    }

また、再帰関数として実装する方法もありますが、 $n$ が大きくなるとスタックオーバーフローの原因になるため注意が必要です。

行列の漸化式から求める

行列を利用すると、整数のままで、しかも高速に計算できます。

2 次正方行列 $A$ を用いて
$\begin{array}{r} (\begin{array}{c} a_{n + 2} \\ a_{n + 1} \end{array}) = A (\begin{array}{c} a_{n + 1} \\ a_{n} \end{array}) \end{array}$
と表すことを考えると、定義の漸化式から
$\begin{array}{r} A = (\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}) \end{array}$
とすればよいです。したがって、
$\begin{array}{r} (\begin{array}{c} a_{n + 1} \\ a_{n} \end{array}) = A^{n} (\begin{array}{c} a_{1} \\ a_{0} \end{array}) = A^{n} (\begin{array}{c} 1 \\ 2 \end{array}) \end{array}$

これで $A^{n}$ を計算すると $a_{n}$ を求めることができ、繰り返し二乗法により、時間計算量は $O (\log n)$ です。
任意の $a_{0}, a_{1}$ に対しても同様です。
値の桁が大きくなることを無視すれば (例えば、値を剰余群で考える場合)、 $n$ が 64 ビット整数の最大値であったとしても一瞬で計算できます。