フィボナッチ数列
$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]
フィボナッチ数列とモナリザ?
Google Bard にフィボナッチ数列について質問しました。
[Q] フィボナッチ数列について、中学生にもわかるように教えてください。
[Bard] フィボナッチ数列は、1と1から始まり、それ以降の各数は前の2つの数の合計である数列です。数列は次のようになります。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, …
フィボナッチ数列は、自然界、金融市場、コンピュータサイエンスなど、さまざまな分野で見つけることができます。また、美しく調和のとれたパターンを作成するため、芸術や建築でも使用されています。
[Q] もっと詳しく説明してください。
[Bard] フィボナッチ数列は、自然界でよく見られます。たとえば、松ぼっくりの鱗の数、ひまわりの種の数、サボテンの棘の数はすべてフィボナッチ数です。フィボナッチ数列は、金融市場でも見られます。たとえば、株価の動きや通貨の為替レートは、フィボナッチ数列によって予測できます。フィボナッチ数列は、コンピュータサイエンスでも使用されます。たとえば、画像圧縮や暗号化アルゴリズムには、フィボナッチ数列が使用されます。フィボナッチ数列は、美しく調和のとれたパターンを作成するため、芸術や建築でも使用されています。たとえば、レオナルド・ダ・ヴィンチのモナリザは、フィボナッチ数列に基づいて作成されています。
[Q] モナリザがフィボナッチ数列に基づいて作成された、とはどういう意味ですか?
[Bard] モナリザは、レオナルド・ダ・ヴィンチによって描かれた絵画です。16世紀に描かれた最も有名な絵画の1つです。絵画は女性の肖像画で、微笑みが特徴です。モナリザはフィボナッチ数列に基づいて作成されたという理論があります。この理論は、絵画の寸法、女性の顔の特徴、絵画の構図がすべてフィボナッチ数列に基づいていると述べています。理論は、フィボナッチ数列が美しく調和のとれたパターンを作成するため、モナリザの作成に使用された可能性があると述べています。フィボナッチ数列は、自然界でも見られる数列であるため、ダ・ヴィンチは絵画に自然の美しさを表現するために数列を使用した可能性があります。ただし、この理論を裏付ける科学的証拠はありません。理論は、ダ・ヴィンチがフィボナッチ数列を知っていたという証拠がないにもかかわらず、ダ・ヴィンチがフィボナッチ数列を使用した可能性に言及しているだけです。