studies

いろいろ勉強用備忘録的な感じ

フィボナッチ数をたくさん出力すると放物線が現れる件

前回、pythonを使ってフィボナッチ数の第n項を返す関数をいくつかのバリエーションで実装した。
ところで、pythonではメモリが許す限りいくらでも大きな整数を扱うことができる。
調子に乗って、前回作った関数でフィボナッチ数を(各項の間にスペースを一個入れながら)、大量に出力してみていると、面白いことに気づいた。
放物線が現れるのである。

f:id:developingskills1110:20170126194748p:plain

おお。
なんだこれは。

若干の感動を覚えつつ、少し考えてみると理由が分かった。

おおざっぱに説明してみよう。

フィボナッチ数列 \{F_n\} とかく。
フィボナッチ数列の漸化式を解くと、一般項は、

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

である。ここで \phi黄金比である。
 1 < \phi < 2であり、したがって -1 < 1 - \phi < 0であるから、

    \begin{eqnarray}\lim_{n\to\infty}(1-\phi)^{n} = 0\end{eqnarray}

ゆえに、nが十分大きいとき、

    F_n \sim O\left(\frac{\phi^{n}}{\sqrt{5}}\right) \sim O(\exp(n))

と評価される。
つまりnが十分大きくなると、その挙動は「指数関数的」になる。


いま、各項は10進数でコマンドラインに表示しているので、各項の桁数は 1 + \lfloor\log_{10} F_n\rfloorである。
先の評価も考慮すれば、第n項の桁数は

    O(\log_{10} \exp(n)) \sim O(n)

で評価されることが分かる。
つまり、フィボナッチ数の各項の桁数はおおよそ「線形」に増えていく。

ところで、上のコマンドラインに放物線が現れたのは、スペースがある適当な間隔で表示されたことが直接の原因である。
ここで、「適当な間隔」というのは、ここまでで議論してきたフィボナッチ数の各項の桁数であり、それはおおむね線形に増加しているのだった。
そこで、長さがO(n)の文字列を繰り返し表示すれば(そして、各文字列のあいだに適当な文字を挟めば)、別にフィボナッチ数列でなくても、同じように放物線が現れそうだと予想がつくだろう。
以下のコードで試してみると、確かにそうなっている。

for i in range(200):
    print(" "*i, end="*")

f:id:developingskills1110:20170126202727p:plain

では、なぜこのような状況で放物線が現れるのか。

次の図で説明する。

f:id:developingskills1110:20170126202835p:plain

コマンドライン下に向かってx軸を、右に向かってy軸をとる。
コマンドラインの左端がy=0で、右端がy=Cである。

各*はxが整数である点に現れていると考え、その座標を、(n, y_n)とする。
上で定義した状況は、図に示した赤色の線の長さの合計が線形に増加する、という状況だから、次のように言い換えられる。

   数列 \{L_n = (C-y_n) + y_{n+1}\}は、等差数列である

これは、Cという定数を抜きにして考えることで、すぐに次のように言い換えられる。

   数列 \{y_n\}の階差数列は、等差数列である

したがって、

    y_n \sim O(n^{2})

が分かり、これにより、放物線が現れることが説明される。
(ほんとうは、離散的な点集合のみで、線は一つも現れてないですけどね)。

あまり、正確には議論していないですが、今日のところはTeXを初めて書いた面倒くささなどもあり、これで

Q.E.D.

ということで許してください。