メモ: Sternの2原子数列
先日の数学デーにて面白い話を聞けたので、忘れないうちにメモを残しておきます。
以下のように定義される数列 はSternの2原子数列（Diatomic Series）と呼ばれるものです。
\begin{align}
s_0 &= 0 \\
s_1 &= 1 \\
s_{2n} &= s_n \\
s_{2n+1} &= s_n + s_{n+1}
\end{align}
実際に漸化式に従って数列を書き並べてみると、こんな感じになります。
\begin{align}
0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, \cdots
\end{align}
から先頭5000個をPythonでプロットしてみた結果がこんな感じです。
プロットを見ていただけると分かると思いますが、増加の速度はそこまで速くありません。 までの最大値でもまだ350程度というところです。
自然対数よりは増加は速く、1次関数くらいに見えます。
さて、初めて見る人からすればとても奇妙な数列ですが、上のような定義のおかげでいくつかのこれまた奇妙な性質を持っています。それが主に次の2つで、
・ の連分数展開が
の2進数表記と対応する
というものです。
前者を用いることによって自然数の集合と（正の）有理数の集合の濃度が等しいことを示せますが、これはカントールによる発見よりも早いそうです。（スターン自身は濃度についての言及はしていないそうです）
後者が成り立てば前者は自明に成り立つ*1*2ので、ここでは少し後者の話をします。
連分数展開と2進数
一つだけ例をだします。 とします。
です。
と
が必要なので計算すると、
\begin{align}
s_{494} &= 19 \\
s_{495} &= 24
\end{align}
となります。従って、隣接項の比が ということです。
次にこれを連分数展開します。
\begin{align}
\frac{19}{24} = 0 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{4} } } }
\end{align}
正則連分数になるのでこの連分数は [0; 1, 3, 1, 4] と書けます。このとき連分数の要素が奇数個になるよう約束しておきます。
このとき、不思議なことに上の連分数の要素と494の2進数表記が対応します。
494の2進数表記である111101110を桁の小さい方から、同じ数がいくつ続くかを見てみてください。ただし、最初は必ず1が何個と数え始めます。
この場合小さい方から読むと、1が0個、0が1個、1が3個、0が1個、1が4個です。
もう一回連分数の要素を見返してみます。[0; 1, 3, 1, 4] です。
なんと、ぴったり対応します！ これを逆に使うと、連分数展開からもとの を復元できます。
また、極限操作と組み合わせれば任意の正則連分数で表現できる実数に収束する公式を作ることが可能です。
