[ 数学 ] なんて美しいんだ！フィボナッチ数列の n 番目の数字を計算する式（Binet の公式）

[サイトマップを見る ]

目的

フィボナッチ数列というは，次のような数列です。

$$
1, 1, 2, 3, 5, 8 ,13, 21, 34, 55, ...
$$

11 番目の数字はなんでしょう。$${34+55=89}$$ ですね。足すだけで簡単です。では，2025 番目の数字はなんでしょう。11 番目までしかわかっていなければ，あと 2014回計算しないといけないですね。2014回は，よーし，やってやろうと実際に計算してみると…

708739281611457476840392281865136184684660304743201296231103660729922630075560975201606226594432287851577966284847213232966198058619678137473911540218932191013152479199052491395990613829783128633838584907764811119848269943975666411947461591085222709920222582895095173197578779620004558118405357685972773449140881728573136145989105271337481634936292350733752455932224934685220663678832984916829760571019760883546960152231936

ぎゃー！とんでもない数字になりました。なんと 423桁の数字です。うわー。
じゃあ，10000番目はとか言われたら，もう計算するのはしんどいです。

Binet の公式

フィボナッチ数列の n 番目を計算する公式があり，それを Binet の公式といいます。ビネーと読みます。フランス人の名前です。こんなかたちをしています。

$$
F(n) = \frac{ \phi^n - (1-\phi)^n }{\sqrt{5}}
$$

$${\phi}$$ というのは黄金比でおよそ $${1.618 \cdots}$$ です。無理数で計算には以下の式を使います。

$$
\phi = \frac{ 1+\sqrt{5} }{2}
$$

Python のコード

10000 乗の計算を手計算でできないので，Python を使うことにします

import sys
import gmpy2

def binet_gmpy2(n):
    phi = gmpy2.mpfr((1 + gmpy2.sqrt(5)) / 2)
    return int(gmpy2.floor((phi**n - (1-phi)**n) / gmpy2.sqrt(5)))

result = binet_gmpy2(int(sys.argv[1]))
print(result)

結果は以下のとおり。

33644764876443076414068973007330955710381117238277605852126866480812554991412454513839997662314414112831298258456008686950873242684486723032698418418175467585935547978350457924182522631291662632959610298569406076827704263774406748467801632720923928299039978263397720092140261650085598224988882418980346239839215461134796497022577651033068735776720495711513163503464282045477336918756785716735379663971038394393122648149790431258986012456257159518476307240586808152716756015706529356850392479778842297440345195122493432605081913316580077562525200592757455911004742903498779532274393313510916793901852327042174553510972298220178341912528356267085390231760640556046211500630869515082705554866094300015582243758557407510322986623659022678148948691142697017915969344115925544633955787315573438677138168815119643755854530606017902173294357562539334484702855601998755779143952700131326175127901540025338825222038516010841920973859138344540889621992651966440891282120292100327123272340315168703290448143724860125647521803237531319205670880730833123730052100567459667261849334991822623274228705634805990508576249548172424100483483266166486535358808669657110447740143303480677725132036726168186871167367416970793084026569882130492438515281889222062865799721972162323751161574793576323829821039088116264032995360320076092501019101387422713403299398570577697550796757215882350824119319867591788846611877077892479167894523475900238361162789421126353413627385782195474167177227693811845785450261695407636522378880632627243819052906303314043721044463497876255928367199353253793895934769350336459625924446061117121231595665044998963593116551800246152924015779002205759689319098478891550428719731911158658425812528455876088115850727902399733786354999325193070205351777838336187158063195626644081473006086422106828221264960432975494191148022634718265604029321239965316468958428800941906155805544799365974250439698706309549098609501997826604454332115864006535829307231381263222272498845513375170211708682772326952892909006567419525381454645210161939610292053542589638698117986724531148393160525849052334522368

2090桁です。

あー，美しい式。どうしてああいうかたちになるのかは別の記事で説明します。

より学びたい方

わたしが好きな先生です。
中学2年生くらいから読むことができます。

• 遠山啓「数の不思議」（SB Creative）

小学校6年生の算数の知識があれば，読み始められます。

• 吉田 信夫 (著)「ガウスとオイラーの整数論の世界」（技術評論社）

[ サイトマップを見る ]