2進数でフィボナッチ数列

こんなニュースを読みました。

15歳女子が「フィボナッチ数列は２進数でも美しいのか」を考察　算数・数学の自由研究作品コンクール「MATHコン」で日本数学検定協会賞を受賞

確かに興味深いですね。フィボナッチ数列は一般的に以下のように定義されます。

数学で、最初の二項が1で、第三項以降の項がすべて直前の二項の和になっている数列。すなわち、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…という数列のこと。
――デジタル大辞泉｜大辞泉｜小学館より

フィボナッチ数列の２進表現は以下のようになります。

fibonacci

0
1
1
10
11
101
1000
1101
10101
100010
110111
1011001
10010000
11101001
101111001
1001100010
1111011011
11000111101
101000011000
1000001010101
1101001101101
10101011000010
100010100101111
110111111110001
1011010100100000
10010010100010001
11101101000110001
101111111101000010
1001101100101110011
1111101100010110101
11001011001000101000
101001000101011011101
1000010011110100000101
1101011100011111100010
10101110000010011100111
100011001100110011001001
111000111101000110110000
1011100001001111001111001
10010101000111000000101001
11110001010000111010100010
110000110010111111011001011
1001110111101000110101101101
1111111110000000110000111000
11001110101101001100110100101
101001110011101010010111011101
1000011101001010011111110000010
1101101011100111110010101011111

2進数を画像のピクセルで表現してみる

規則性がありそうでなさそうな……。文字列では分かりにくいので2進数列の1ビットを1ピクセルにして画像にしてみましょう。

画像処理にはpythonのPillowライブラリを使います。

Pythonで画像のピクセル操作 - Qiita

先ほどの一覧の０を白、１を黒で描画します。ピクセルは位を揃えるために右詰めにしてあります。また、上から下に計算していくので下に行くほど桁数が多くなります。

fibonacci.py

#!/usr/bin/python3

from PIL import Image

""" 1,000 x 1,000で出力 """
length = 1000

""" フィボナッチ数列のジェネレーターを定義 """
def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, b+a

""" キャンバスを用意 """
canvas = Image.new('RGB', (length, length), (255, 255, 255))

fibgen = fibonacci()

for y in range(length):
    """
    フィボナッチ数列を取り出して、2進数表現に変換、最初の「0b」をカットしたリストを作ります
    """
    fiblist = bin(fibgen.__next__())[2:]

    for x in range(length):
        if x == len(fiblist):
            break
        """ ピクセルを右づめにするための計算 """
        rx = x + (length - len(fiblist))
        if fiblist[x] == '1':
            canvas.putpixel((rx, y), (0, 0, 0, 0))
        else:
            canvas.putpixel((rx, y), (255, 255, 255, 0))

canvas.save('fibonacci.png', 'PNG')

出力結果が以下。右端の数bitは明らかに規則性が見られます。図に倒立した直角三角形が頻出してるのも特徴ですね。一次元セル・オートマトンにどこか似たところを感じます。

拡大してよく見ると、白や黒の逆三角形は必ず縞模様の帽子をかぶっていたり、突然市松模様や十字模様、斜め縞模様などが現れるなど非常に興味深い結果となっています。

上記の画像サイズは1,000x1,443です。

ギャラリー

演算結果からお気に入りのパターンを抜粋してみました。2進数のフィボナッチ数列は、その性質上、あるビット列がその直前2列の状態に依存するため、一種のセル・オートマトンと言えるのかも知れません。

画像	コメント
	よく出てくる三角帽子くん
	ななめ縞模様
	白黒兄弟
	市松模様と帽子くん

ランダムノイズ

比較のために、上記の画像と同じ領域に50%の確率で白と黒に別れるランダムなノイズを詰めたものが下記になります。フィボナッチ数列の図（上図）に見られる特徴が乱数（下図）には見られないことが分かりますね。