フィボナッチ数列とゼッケンドルフの定理

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。

はじめに

最近の の投稿は、例えばシルベスター数列などの数学の分野で合成数の数列をよく扱っております。恐らく最も有名な数列であるフィボナッチ数列については取り上げていなかったので、本稿はフィボナッチ数列についての軽めの話題から。

フィボナッチ数列

言わずと知れた数列ですが、定義は以下。

漸化式 $F _{0} = 0,\quad F _{1} =1,\quad F _{n} = F _{n-2} + F _{n-1}\ (n\ge 2)$
で定まる数列を『フィボナッチ数列』といいます。

Haskellで簡単に書くと次のようになります。

フィボナッチ数列

fibs@(_ : tfibs) = 0 : 1 : zipWith (+) fibs tfibs

少し前のGHC 8.6の頃ですが、効率的なプログラムの考察は @mod_poppo さんの次のエントリーが詳しくて、zipWith'（正格評価）による再帰的なプログラムの方が良いようです。ただし、本稿では計算効率は追求せずに、上記を使います。

ゼッケンドルフの定理

任意の正の整数は、1つ以上の、番号が連続しないフィボナッチ数の和として一意に表せるという定理です。数式を用いて示すと以下のようになります。（Wikipedia「ゼッケンドルフの定理」より）

$N$ を任意の正の整数とすると、$c_{i+1} \gt c_{i} + 1$ を満たす正の整数 $c_{i} \ge 2$ が存在して、

$\displaystyle N = \sum _{i=0}^{k} F _{c _{i}}$

（ただし $F_{n}$ は $n$ 番目のフィボナッチ数）

このような和を $N$ のゼッケンドルフの表現と呼びます。
この定理の証明は Wikipedia にも記載がありますが、次のマスオさんらのサイトに分かりやすい証明が載っています。

さて、この定理から $n$ のゼッケンドルフ表現をリストで求めるプログラムは、次のようになります。これは「その数を超えない最大のフィボナッチ数を取っていく」という方法で求めます。

ゼッケンドルフ表現

zeckendorf n = zec n (reverse $ takeWhile (<=n) fibs) where zec 0 _ = []; zec m (f:fs) | f <= m = f : (zec (m-f) (dropWhile (>m-f) fs)) | otherwise = zec m fs; zec _ [] = error ""

Wikipedia 等で、例として挙げられる $n = 100$ で試してみましょう。

ghci> zeckendorf 100
[89,8,3]

この定理に名を残すエドゥアルド・ゼッケンドルフ（1901/5/2 - 1983/5/16）は、ベルギーの医師・陸軍将校（軍医）であり、アマチュアの数学者でした。このフィボナッチ数列の研究が有名で、ほかにも数論に関する20以上の論文を主に発表した方だそうです。

ここで、ゼッケンドルフ表現では何個のフィボナッチ数で表現できるのかという疑問が湧きました。次のように検証してみました。

ghci> foldr max 0 $ length . zeckendorf <$> [1..10]
2
ghci> foldr max 0 $ length . zeckendorf <$> [1..100]
5
ghci> foldr max 0 $ length . zeckendorf <$> [1..1_000]
7
ghci> foldr max 0 $ length . zeckendorf <$> [1..10_000]
9
ghci> foldr max 0 $ length . zeckendorf <$> [1..100_000]
12
ghci> foldr max 0 $ length . zeckendorf <$> [1..1_000_000]
14
ghci> foldr max 0 $ length . zeckendorf <$> [1..10_000_000]
17

おわりに

ここで紹介したゼッケンドルフ表現は、ワイソフのゲーム（2山の片方からまたは、両方から同数ずつ取る石取りゲーム）の後手必勝形とも関係があるそうです。ご興味のある方は Wikipedia：ワイソフのゲーム もご参照ください。

最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。

• macOS: Sonoma 14.6.1 (chip: Apple M1)
• GHCup: 0.1.30.0
• GHC: 9.6.6

ご一読いただきまして有り難うございます。

（●）（●） Happy Hacking!
/""　＿＿""＼