4.Fibonacci数、Lucas数、Lucas列の定義


Lucas列とは、Fibonacci数、Lucas数等を一般化したものである。
一般化することにより、これらの数列が持っている性質を理解しやすくなる。
Lucas列が持つ性質の応用範囲としては、以下のようなものがある。

後者2つはp+1法と呼ばれているものである。これについては、12章で触れる。

Fibonacci数

Fibonacci数の定義は以下のとおりである(読み方は「フィボナッチ」。人名である)。

F0=0
F1=1
Fn+1=Fn+Fn-1(n≧1)

最初のいくつかを書き下すと、以下のとおり。

F0=0
F1=1
F2=1
F3=2
F4=3
F5=5
 ……

n番目の Fibonacci数を求めてみよう。
上記定義をそのままプログラムにすると、以下のようになる。

 10   ' Fibonacci
 20   ' F(0)=0, F(1)=1, F(n+1)=F(n)+F(n-1)
 30   fnfib(N)
 40   local Y,Y0,Y1,I
 50   if N=0 then return(0)
 60   if N=1 then return(1)
 70   Y0=0:Y1=1:I=1
 80   repeat
 90     Y=Y1+Y0:inc I:Y0=Y1:Y1=Y
100   until I=N
110   return(Y)

このアルゴリズムは、ループ回数がnのオーダなので、大きなnに対する計算には向かない。

Lucas数

Lucas数の定義は以下のとおりである(読み方は「リュカ」。人名である)。

L0=2
L1=1
Ln+1=Ln+Ln-1(n≧1)

最初のいくつかを書き下すと、以下のとおり。

L0=2
L1=1
L2=3
L3=4
L4=7
L5=11
 ……

n番目の Lucas数を求めてみよう。
上記定義をそのままプログラムにすると、以下のようになる。

 10   ' Lucas
 20   ' L(0)=0, L(1)=1, L(n+1)=L(n)+L(n-1)
 30   fnluc(N)
 40   local X,X0,X1,I
 50   if N=0 then return(2)
 60   if N=1 then return(1)
 70   X0=2:X1=1:I=1
 80   repeat
 90     X=X1+X0:inc I:X0=X1:X1=X
100   until I=N
110   return(X)

このアルゴリズムは、ループ回数がnのオーダなので、大きなnに対する計算には向かない。

さて、ここまでの記述は、Fibonacci数の時とほとんど同じである。違うのは初期値だけ。
両者は以下に示すLucas列の特別な場合に相当する。

Lucas列

上記の拡張として、

y0=0
y1=1
yn+1=a・yn+b・yn-1(n≧1)

x0=2
x1=1
xn+1=a・xn+b・xn-1(n≧1)

と定義する。これをLucas列と呼ぶ。
a=b=1とおいた時、ynが Fibonacci数、xnが Lucas数に相当する。

2次方程式 t2−at−b=0の判別式をd=a2+4b、2根を

α=(a+sqrt(d))/2
β=(a−sqrt(d))/2

とおくとき、yn、xnは、以下の式で表すことができる。

yn=(αn−βn)/(α−β)
xn=αn+βn


このLucas列には以下のような性質がある。

これにより、Fibonacci数 F2nは、FnとLucas数 Ln の積に素因数分解されることがわかる。

これも、Fibonacci数の素因数分解に役立つ。

これは、Lucas数の素因数分解に使える。


この章の目次

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典