フィボナッチ数

数列を構成する数
テトラナッチ数から転送)

フィボナッチ数(フィボナッチすう、: Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)に因んで名付けられたである。

フィボナッチ数を一辺とする正方形
ウィキペディア日本語版メインページ2007年2012年)で使われていたイメージ画像もフィボナッチ数列を利用していた[注釈 1]

概要

編集

フィボナッチ数列フィボナッチすうれつ: Fibonacci sequence(Fn) は、次の漸化式で定義される:

 

第0~22項の値は次の通りである:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …(オンライン整数列大辞典の数列 A000045

1202年にフィボナッチが発行した『算盤の書』(Liber Abaci) に記載されたことで「フィボナッチ数」と呼ばれているが、それ以前にもインドの学者であるヘーマチャンドラ (Hemachandra) が韻律の研究により発見し、書物に記したことが判明している[1][2]

兎の問題

編集

レオナルド・フィボナッチは次の問題を考案した[3]

  • 1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
  • 兎が死ぬことはない。
  • この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか?

つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。

産まれたばかりのつがい 生後1か月のつがい 生後2か月以降のつがい つがいの数(合計)
0か月後 1 0 0 1
1か月後 0 1 0 1
2か月後 1 0 1 2
3か月後 1 1 1 3
4か月後 2 1 2 5
5か月後 3 2 3 8
6か月後 5 3 5 13
7か月後 8 5 8 21
8か月後 13 8 13 34
9か月後 21 13 21 55
10か月後 34 21 34 89
11か月後 55 34 55 144
12か月後 89 55 89 233

一般項

編集

フィボナッチ数列の一般項は次の式で表される[3]

 

この式は1843年ビネ (Jacques Philippe Marie Binet) が発表したことからビネの公式と呼ばれるが、それ以前の1730年ド・モアブル)・1765年オイラー)にも発表されており、ビネは最初の発見者ではない。

なお、この式に現れる

 

黄金数で、いくつかの数学的特徴がある。黄金数を作る二次方程式 x2x − 1 = 0 の解を α, β (α > β) とすると、上記の一般項は

 

と表せる。

また、一般項の第2項 1/ 5 (−φ)n の絶対値は減少列で、n = 0 のとき 1/ 5 = 0.447... < 1/2 より、第2項を切り捨てた式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。

 

この誤差の絶対値は0.5未満なので、Fn の正確な整数値は以下の式で得られる[3]

 

ただし、x床関数である。

なお、後述の負数番への拡張を考慮した場合、n < 0 では逆に一般項の第1項の絶対値が0.5未満となるため、n < 0 における Fn の正確な整数値は以下の式で得られる。

 

これらのことから、任意の整数 n における Fn の正確な整数値は以下の式で得られる。

 

ただし、sgn x符号関数である。

行列表現

編集

また、フィボナッチ数列の漸化式は次のように行列表現できる[3]

 

これらを並べて表記すると、

 
 

ここで、F−1 = 1 は、漸化式 Fn = Fn−1 + Fn−2n = 1 を代入すると得られる(詳細は後述の負数番への拡張を参照)。

更に、n2n で置換すると、

 

よって、

 

母関数

 

である。

また、この行列表現を基に、以下のような漸化式を考えることが出来る。

 

性質

編集

フィボナッチ数列の隣接2項の商は黄金数 φ に収束する。この性質は初期値 (F0 = 0, F1 = 1) に依らない。

 

これは次のように導出される:

  が収束するとすれば、
 
 
  • 自然数 p, q最大公約数r とすると、FpFq の最大公約数は Fr である。

これより以下を導くことができる。

  • mn で割り切れるならば、FmFn で割り切れる。
  • 連続する2数は互いに素であることより、隣り合うフィボナッチ数も互いに素である。
  • Fm偶数となるのは m が 3 の倍数となるときと一致する。
  • Fm が 5 の倍数となるのは m が 5 の倍数となるときと一致する。
  • p が 2 でも 5 でもない素数のとき、m = p − (5/p) とおくと pFm を割り切る。ここで ( / )ルジャンドル記号である。

フィボナッチ数の累和や累積について以下の式が成り立つ。

  • F1 + F2 + F3 + … + Fn = Fn+2 − 1
  • F1 + F3 + F5 + … + F2n−1 = F2n
  • F2 + F4 + F6 + … + F2n = F2n+1 − 1
  • F12 + F22 + F32 + … + Fn2 = Fn Fn+1
  • Fn−1 Fn+1Fn2 = (−1)n

また、次の関係式が知られている。

 

フィボナッチ数のうち平方数であるのは F1 = F2 = 1, F12 = 144 のみ (Cohn 1964)[4]立方数であるのは F1 = F2 = 1, F6 = 8 のみ (London and Finkelstein 1969)[5]である。フィボナッチ数のうち累乗数であるのはこれしかない (Bugeaud, Mignotte, Siksek 2006)[6]。(オンライン整数列大辞典の数列 A227875

フィボナッチ数で素数であるのは 2, 3, 5, 13, 89, 233, 1597, 28657, … である(オンライン整数列大辞典の数列 A005478)。また、これらはフィボナッチ素数と呼ばれる。

フィボナッチ数で三角数であるのは 1, 3, 21, 55オンライン整数列大辞典の数列 A039595)のみであることは Vern Hoggatt によって予想されていたが、のちに Luo Ming によって証明された[7]

フィボナッチ数でハーシャッド数であるのは 1, 2, 3, 5, 8, 21, 144, 2584, …(オンライン整数列大辞典の数列 A117774)。

フィボナッチ数は完全数にはならない[8]。より一般に、フィボナッチ数は倍積完全数にもならず[9]、2つのフィボナッチ数の商も完全数にはならない[10]

フィボナッチ数列の逆数和は収束し、記号 ψ で表される。

 [11]

この ψ が無理数であることは証明されているが (André-Jeannin 1989)、超越数であるかどうかは分かっていない。

任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる(ゼッケンドルフの定理)。

プログラミング言語での実装

編集

再帰的処理の例としてよく紹介される。以下はPythonでの例。

ただし、下記実装例の内、#負数番への拡張に対応しているのは例5・例6のみである。

例1(再帰的処理による実装例)

編集

このプログラムでは、n が与えられてから Fn が求まるまでに Fnφn 回の関数呼び出しが発生する(すなわち指数時間の計算となる)ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる他、後述するように様々な実装例が検討されている。

def fib(n: int) -> int:
    if n < 2:
        return n
    else:
        return fib(n=n-1) + fib(n=n-2)

メモ化の例を挙げると[注釈 2]

from functools import cache

@cache
def fib(n: int) -> int:
    if n < 2:
        return n
    else:
        return fib(n=n-1) + fib(n=n-2)

例2(ループ処理による実装例)

編集
def fib(n: int) -> int:
    a, b = 1, 0
    for _ in range(n):
        a, b = b, a+b
    return b

例3(指数関数的なコールを必要としない再帰的処理による実装例)

編集

n が1以上の場合に第2・第3の引数を上記例2と同じ要領で順次更新していくことで、コール回数を n 回に抑えられる為、線形時間で処理出来る。

def fib(n: int, a: int = 1, b: int = 0) -> int:
    if n == 0:
        return b
    else:
        return fib(n=n-1, a=b, b=a+b)

例4(対数時間での再帰的処理による実装例)

編集

#行列表現で導出した漸化式(以下に再掲)を用いることで、再帰的処理でも対数時間で処理出来る。

 

ただし、プログラム上は0を掛けるからと言ってその対象の値が計算されない訳では無い為(短絡評価されない)、条件式による分岐で表記している。

def fib(n: int) -> int:
    if n < 2:
        return n
    q = n // 2
    fq = fib(n=q)
    return fq ** 2 + (2 * fib(n=q-1) * fq if n % 2 == 0 else fib(n=q+1) ** 2)

例5(一般項による実装例)

編集

浮動小数点型を使用すると計算誤差が発生する為、decimalモジュールを用いている[注釈 3]

from decimal import Decimal

SQRT5 = Decimal(5).sqrt()
PHI = (1 + SQRT5) / 2 # 黄金数

def fib(n: int) -> int:
    return round((PHI ** n - (-PHI) ** -n) / SQRT5)

なお、先述の通りフィボナッチ数列の一般項は、引数 n の符号によって2項の内いずれかが0.5未満となることから、符号関数及び床関数を用いて以下のように表すことが出来た。

 #一般項より再掲)

このことから、以下のように実装することで冪乗演算の回数を減らすことが出来る[注釈 4]

from decimal import Decimal

ONE = Decimal(1)
SQRT5 = Decimal(5).sqrt()
PHI = (1 + SQRT5) / 2 # 黄金数

def fib(n: int) -> int:
    if n == 0:
        return 0
    sgn_n = ONE.copy_sign(n)
    return sgn_n * round((sgn_n * PHI) ** abs(n) / SQRT5)

例6(行列表現での実装例)

編集
 #行列表現より再掲)

より、nn − 1 に置換すると、

 

従って、Fn は、上式右辺(の具体的な計算値)の左上成分に等しい。

行列の冪を簡潔に記述する為にSymPyを用いた[注釈 5][注釈 6]

from sympy import Matrix

def fib(n: int) -> int:
    return (Matrix([[1, 1], [1, 0]]) ** (n - 1))[0, 0] # 左上成分

その他の話題

編集
 
ヒマワリの種は螺旋状に並んでおり、螺旋の数を数えていくとフィボナッチ数が現れる[12]
  • フィボナッチ数は自然界の現象に数多く出現する。
  • また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。

ヨハネス・ケプラーは1611年に発表した小論文「新年の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた[13]

  • アブラナダイコン花びらは4枚であり、植物学では花式図より3数性、4数性、5数性で分類される[15][16]
  • 植物に現れる螺旋の数もフィボナッチ数であることが多い。
    • ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある[17]
  • パイナップルの螺旋の数は時計回りは13、反時計回りは8になっている。
  • 葉序(植物の葉の付き方)はフィボナッチ数と関連している。(シンパー=ブラウンの法則)
  • らせん葉序におけるシンパー・ブラウンの法則はフィボナッチ数列と関連するが、「近似値を示すにすぎず、またこれにあてはまらない例もある」(岩波生物学辞典)。
  • ハチアリなど、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる(父母2匹、祖父母3匹、曽祖父母5匹、高祖父母8匹…)。
  • n 段の階段を1段または2段ずつ登るときに、登る場合の数は Fn+1 通りある。
  • ●と○を合わせて n 個並べる。●が2個以上続かないように一列に並べる方法は Fn+2 通りある。
  • 為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。

負数番への拡張

編集

フィボナッチ数列は、漸化式 Fn = Fn−1 + Fn−2 を全ての整数 n に対して適用することにより、n が負の整数の場合に拡張できる。そして Fn = (−1)n+1Fn が成り立つ。この式より、負の番号の項は次のようになる。

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
F−n 0 1 −1 2 −3 5 −8 13 −21 34 −55 89 −144 233 −377 610 −987 1597 −2584 4181 −6765

類似の数列

編集

フィボナッチ数列の定義である初期値や漸化式をやや変更して、類似の数列が作れる。

項数の変更

編集

フィボナッチ数列は各項が先行する二項の和であるものであったが、それを「先行する k 項の和」と置き換えた一般化

 

を考えることができる。ただし、初期値は 1 で埋める(1-fil型)

 

あるいは 0 で埋める(0-fil型)

 

などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ[注釈 7]

和の項数や初期値の変更
k 接頭辞[18] 名称 整数列大辞典
3 tri- トリボナッチ数 0 fil: A000073
1 fil: A000213
4 tetra- テトラナッチ数 0 fil: A000078
1 fil: A000288
5 penta- ペンタナッチ数 0 fil: A001591
1 fil: A000322
6 hexa- ヘキサナッチ数 0 fil: A001592
1 fil: A000383
7 hepta- ヘプタナッチ数 0 fil: A122189
1 fil: A060455
8 octa- オクタナッチ数 0 fil: A079262
1 fil: A123526
9 nona- ノナ(ボ)ナッチ数 1 fil: A127193
10 deca- デカ(ボ)ナッチ数 1 fil: A127194
11 undeca- ウンデカ(ボ)ナッチ数 1 fil: A127624
12 dodeca- ドデカ(ボ)ナッチ数 1 fil: A207539
20 icosa- イコサナッチ数

トリボナッチ数

編集

特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが0番目からのものは

T0 = T1 = 0, T2 = 1,
Tn+3 = Tn + Tn+1 + Tn+2 (n ≥ 0)

と表される。第0~21項の値は次の通りである:

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (OEIS A000073)

トリボナッチ数列の一般項は次で表される。

 

ただし、α, β, γ三次方程式 x3x2x − 1 = 0 の3解

 

であり、ここで

 1 の虚立方根

である。

また、上記の αトリボナッチ定数という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する:

 

テトラナッチ数

編集

直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット0番の 0-fil型は

T0 = T1 = T2 = 0, T3 = 1,
Tn+4 = Tn + Tn+1 + Tn+2 + Tn+3 (n ≥ 0)

と書けて、第0~21項の値は次の通りである:

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, … (OEIS A000078)

一般項は、四次方程式 x4x3x2x − 1 = 0 の4解を α, β, γ, δ として、

 

となる。

初期値の変更

編集

リュカ数

編集

フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数という。

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … (OEIS A000032)

この数列の一般項は

 

と表される。

フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列であり、1878年にエドゥアール・リュカが体系的な研究を行い、1913年にロバート・ダニエル・カーマイケル英語版がその結果を整理、拡張した[19]。これらの研究が現代のフィボナッチ数の理論の基礎となった。

脚注

編集

注釈

編集
  1. ^ フィボナッチ数列を利用したこのウィキペディア日本語版のメインページの画像は、利用者:Co.kyoto/メインページ案中の「ウィキペディアにようこそ!」欄の左側に掲載されていた。なお、現在ウィキペディア日本語版のメインページで利用されている、「Template:メインページ/ようこそ」とは異なり、各テンプレートの集合で構成されているため、履歴にはない。
  2. ^ この例では(メモ化の為の)キャッシュサイズが無制限に肥大する。
  3. ^ decimalモジュールの計算精度に依る制約はある(デフォルトでは十進28桁(二進93ビット相当))。
  4. ^ 便宜上0の0乗が何らかの定数(プログラミング言語では0の0乗を1とすることが多く、Pythonにおいてもint型やfloat型で0の0乗を計算した場合は1が返される)を取るものとすれば、上記の式は0を含む任意の整数 n について成り立つ。ただし、decimal型で0の0乗を計算するとエラーとなる為、コード上は n = 0 の場合を予め除外している。
  5. ^ SymPyは、フィボナッチ数を求める関数を自前で持っているが、ここでは使ってない。
  6. ^ 計算速度は、行列の冪を計算する手法に依存する。幸いにしてSymPyのそれは、素朴な方法(冪の数だけ行列を乗算する)よりは速い。
  7. ^ 当然のことだが "Fibonacci" は人名であって、"fibo-" + "-nacci" や "fi-" + "-bonacci" という構成の合成語でもないし、もちろん "fi-" や "fibo-" が "2" の意味を持つわけでもない(ただし、摩擦音 f と破裂音 b が音韻的に近い関係にあることから 2 を表す "bi-" を "fi-" に結び付けての類推ではあるかもしれない)が、「フィボナッチ」の語を頭から適当な音節分だけ倍数を表す接頭辞で置き換えるという、冗談のような名付けになっている。

出典

編集
  1. ^ Parmanand Singh. "Acharya Hemachandra and the (so called) Fibonacci Numbers". Math. Ed. Siwan, 20(1): pp. 28–30, 1986. ISSN 0047-6269.
  2. ^ Parmanand Singh, "The So-called Fibonacci numbers in ancient and medieval India." Historia Mathematica 12(3), pp. 229–244, 1985.
  3. ^ a b c d 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。ISBN 4-87408-414-1 
  4. ^ J. H. E. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39 (1964), pp. 537–540.
  5. ^ London, Hymie; Finkelstein, Raphael (1969), “On Fibonacci and Lucas numbers which are perfect powers”, Fibonacci Quart. 7 (5): 476-481, Part1, Part2, Correction 
  6. ^ Yann Bugeaud, Maurice Mignotte, Samir Siksek, Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. of Math. 163(2006), pp. 969–1018. Yann Bugeaud, Publications, 2006.
  7. ^ Ming, Luo (1989), “On triangular Fibonacci numbers”, Fibonacci Quart. 27 (2): 98-108, https://www.fq.math.ca/Scanned/27-2/ming.pdf 
  8. ^ Luca, Florian (2000). “Perfect Fibonacci and Lucas numbers”. Rendiconti del Circolo Matematico di Palermo 49 (2): 313-318. doi:10.1007/BF02904236. ISSN 1973-4409. MR1765401. 
  9. ^ Broughan, Kevin A.; González, Marcos J.; Lewis, Ryan H.; Luca, Florian; Mejía Huguet, V. Janitzio; Togbé, Alain (2011). “There are no multiply-perfect Fibonacci numbers”. Integers 11a: A7. MR2988067. http://math.colgate.edu/~integers/vol11a.html. 
  10. ^ Luca, Florian; Mejía Huguet, V. Janitzio (2010). “On Perfect numbers which are ratios of two Fibonacci numbers”. Annales Mathematicae at Informaticae 37: 107-124. ISSN 1787-6117. MR2753031. https://ami.uni-eszterhazy.hu/index.php?vol=37. 
  11. ^ Reciprocal Fibonacci Constant -- from Wolfram MathWorld
  12. ^ 数学広場の別名「ひまがり広場」の由来:数学と 黄金花『ひまわり』 (PDF)愛媛県立丹原高等学校
  13. ^ 榎本恵美子 (1977). “翻訳・新年の贈り物あるいは六角形の雪について”. 知の考古学 第11号: 286ページ. 
  14. ^ 聖なる幾何学 スティーヴン・スキナー著 p.63「植物成長の幾何学」より抜粋
  15. ^ 西山豊「花びらの数はフィボナッチ数列に落ち着くか?」『数学文化』No. 39, p104, 2023.3
  16. ^ 西山豊「花びらの数はフィボナッチ数」は本当か?『大阪経大論集』Vol.74, No.6, 125-139, 2024.3
  17. ^ 第14回:全ての植物をフィボナッチの呪いから救い出す(こんどうしげるの生命科学の明日はどっちだ!?)
  18. ^ より多くは、例えば [1] などを見よ
  19. ^ R. D. Carmichael, On the numerical factors of the arithmetic forms α n ± β n, Ann. of Math. 15 (1913), pp.30–70, doi:10.2307/1967797.

参考文献

編集
  • 佐藤修一『自然にひそむ数学―自然と数学の不思議な関係』講談社〈ブルーバックス B-1201〉、1998年1月20日。ISBN 4-06-257201-X 
  • 中村滋『フィボナッチ数の小宇宙(ミクロコスモス)―フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月。ISBN 4-535-78281-4 
    • 中村滋『フィボナッチ数の小宇宙(ミクロコスモス)―フィボナッチ数、リュカ数、黄金分割』(改訂版)日本評論社、2008年1月。ISBN 978-4-535-78492-5 
  • 中村滋「日本フィボナッチ協会の20年」『数学セミナー』第57巻第8号、日本評論社、2018年8月、48-53頁。 
  • Arakelian, Hrant (2014) (ロシア語), Mathematics and History of the Golden Section, Logos, ISBN 978-5-98704-663-0 
  • Dunlap, Richard A. (1997-12-17), The Golden Ratio and Fibonacci Numbers, World Scientific Pub. Co. Inc., ISBN 978-981-02-3264-1 
  • Koshy, Thomas (2017-12-04), Fibonacci and Lucas Numbers with Applications, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, Volume 1 (2nd ed.), Wiley, ISBN 978-1-118-74212-9 
  • Koshy, Thomas (2019-01-07), Fibonacci and Lucas Numbers with Applications, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, Volume 2 (2nd ed.), Wiley, ISBN 978-1-118-74208-2 
  • Leonardo Pisano Fibonacci L. E. Sigler訳 (1987-02-11), The Book of Squares, Academic Press, ISBN 978-0-12-643130-8  - 『平方の書』の英訳。
  • Sigler, Laurence (2003-11-11), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Springer-Verlag, ISBN 978-0-387-40737-1  - 『算盤の書』の英訳。

関連項目

編集

外部リンク

編集