Lucas列とは、Fibonacci数、Lucas数等を一般化したものである。
一般化することにより、これらの数列が持っている性質を理解しやすくなる。
Lucas列が持つ性質の応用範囲としては、以下のようなものがある。
後者2つはp+1法と呼ばれているものである。これについては、12章で触れる。
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数の定義は以下のとおりである(読み方は「リュカ」。人名である)。
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列の特別な場合に相当する。
上記の拡張として、
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数の素因数分解に使える。
前 | この章の目次 | 次 |
---|