フィボナッチ数列
$F_1=F_2=1,\ F_{n}=F_{n-2}+F_{n-1}$ で定義される数列を フィボナッチ数列 とよびます。規則にしたがって最初の $10$ 項を書き並べると以下のようになります。
\[1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55\tag{1}\]
フィボナッチ数列の一般項は
\[F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}\tag{2}\]
によって与えられます (ビネの公式)。ここで $\phi$ は黄金比とよばれる定数で、
\[\phi=\frac{1+\sqrt{5}}{2}=1.6180339887...\tag{3}\]
によって定義されています。フィボナッチ数列の隣り合う項は、この黄金比に収束することが知られています：
\[\lim_{n\rightarrow\infty}\frac{F_n}{F_{n-1}}=\phi\tag{4}\]
漸化式 $F_{n}=F_{n-2}+F_{n-1}$ を満たすように、$n$ を負番号まで拡張することもできます。後述する SymPy の fibonacci() 関数は、負番号のフィボナッチ数も生成できます。
それでは、Python でフィボナッチ数列を実装してみましょう。正の整数 n を与えて、第 n 項までのフィボナッチ数列をリストで返す fibonacci_list() 関数です。
# PYTHON_FIBONACCI_01
# In[1]
# フィボナッチ数列生成関数
def fibonacci_list(n):
fib = [1, 1]
if n == 1:
fib = [1]
else:
for k in range(2, n):
fib.append(fib[k-1]+fib[k-2])
return fib 上のコードは少しだけ工夫して条件分枝の記述を減らしています。最初に変数 fib に [1, 1] を格納し、引数 n に 1 が渡されたときだけ [1] に置き換えます。n に 2 が渡されたかどうかのチェックはしません。n == 2 のときは range(2, 2) が空リストであるために、for 以下の処理は実行されないからです。
$F_1$ から $F_{10}$ のリストを作ってみます。
# In[2]
# フィボナッチ数列を第10項まで求める
fib = fibonacci_list(10)
print(fib)[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
特定のフィボナッチ数だけ欲しいときは、インデックスで参照します。
# In[3]
# 7番目のフィボナッチ数を取得
print(fib[8])34
十分大きな番号の隣り合う 2 項の比が黄金比 $1.6180339887...$ に近い値となることを確認しておきましょう。収束が速いので、それほど多くの項数は必要ありません。
# In[4]
# フィボナッチ数列を第100項まで求める
fib = fibonacci_list(100)
# F(50)/F(49)
phi_1 = fib[49] / fib[48]
# F(100)/F(99)
phi_2 = fib[99] / fib[98]
print(phi_1)
print(phi_2)1.618033988749895 1.618033988749895
計算機代数システム SymPy にはフィボナッチ数あるいはフィボナッチ多項式を生成する sympy.fibonacci() が用意されています。sympy.fibonacci(n) は n 番目のフィボナッチ数を返します。
# PYTHON_FIBONACCI_02
# In[1]
import sympy
# 10番目のフィボナッチ数を生成
fib = sympy.fibonacci(10)
print(fib)55
数列を生成するときはループで処理します。
# In[2]
fib = [sympy.fibonacci(x) for x in range(-5, 5)]
print(fib)[5, -3, 2, -1, 1, 0, 1, 1, 2, 3]
この実行結果を見るとわかるように、sympy.fibonacci(n) は「前の 2 項を足して新しい項を作る」という規則にしたがって負番号に対応するフィボナッチ数も返します。
sympy.fibonacci(n, sym) はフィボナッチ多項式オブジェクトを返します。フィボナッチ多項式 とは、以下の漸化式で定義される多項式列です。
\[\begin{align*}&F_1(x)=0,\ F_2(x)=1\\[6pt]
&F_n(x)=xF_{n-1}(x)+F_{n-2}(x)\quad (n\geq 2)\end{align*}\tag{5}\]
$x=1$ とした場合は、フィボナッチ数列となります。
引数 n, x にシンボルを与えて、n 番目のフィボナッチ多項式を生成してみます。
# PYTHON_FIBONACCI_03
# In[1]
import sympy
x = sympy.Symbol("x")
n = sympy.Symbol("n")
# n番目のフィボナッチ多項式
fib_pol = sympy.fibonacci(n,x)
print(fib_pol)fibonacci(n, x)
n に適当な値を代入することで、任意番号のフィボナッチ多項式が得られます。$F_7(x)$ を取得してみましょう。
# In[2]
fib = fib_pol.subs(n, 7)
print(fib)x**6 + 5*x**4 + 6*x**2 + 1
トリボナッチ数列
トリボナッチ数列 は直前 3 項の和で生成される数列です。
\[T_{n+3}=T_n+T_{n+1}+T_{n+2}\tag{6}\]
最初の 3 項の選び方は色々あります。たとえば、
\[T_1=T_2=1,\ T_3=2\tag{7}\]
とすると、
\[1,\ 1,\ 2,\ 4,\ 7,\ 13,\ 24,\ 44,\ 81,\ ...\tag{8}\]
のように並びます。ちなみに、フィボナッチはイタリアの数学者レオナルド・フィボナッチの名前に由来しますが、トリボナッチという人は存在しません。Python でトリボナッチ数列を実装してみましょう。
# PYTHON_TRIBONACCI
# In[1]
# トリボナッチ数列生成関数
def tribonacci_list(n, t0, t1, t2):
tri = [t0, t1, t2]
if n == 1:
tri = [t0]
elif n == 2:
tri = [t0, t1]
else:
for k in range(3, n):
tri.append(tri[k-1]+tri[k-2]+tri[k-3])
return tri n には生成する数列の項数を指定します。
t0, t1, t2 には最初の 3 項を渡します。
$1,\ 1,\ 2$ から始まる $10$ 項のトリボナッチ数列を表示してみます。
# In[2]
# 1,1,2から始まる10項のトリボナッチ数列を生成
tri = tribonacci_list(10, 1, 1, 2)
print(tri)[1, 1, 2, 4, 7, 13, 24, 44, 81, 149]