C
Fibonacci
Binary

二進数でフィボナッチ数列を考える

先ほど C 言語での二進数表示のアイデアメモ を書いた直後にツイッターを眺めていたら、以下の記事が流れてきました。

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

このシンクロニシティを無駄にしてはならぬと、とりあえず 45 番目まで二進数で表示してみました。
何か見えてくるのでしょうか?

二進数フィボナッチ数列

00000000-00000000-00000000-00000001 1
00000000-00000000-00000000-00000001 1
00000000-00000000-00000000-00000010 2
00000000-00000000-00000000-00000011 3
00000000-00000000-00000000-00000101 5
00000000-00000000-00000000-00001000 8
00000000-00000000-00000000-00001101 13
00000000-00000000-00000000-00010101 21
00000000-00000000-00000000-00100010 34
00000000-00000000-00000000-00110111 55
00000000-00000000-00000000-01011001 89
00000000-00000000-00000000-10010000 144
00000000-00000000-00000000-11101001 233
00000000-00000000-00000001-01111001 377
00000000-00000000-00000010-01100010 610
00000000-00000000-00000011-11011011 987
00000000-00000000-00000110-00111101 1597
00000000-00000000-00001010-00011000 2584
00000000-00000000-00010000-01010101 4181
00000000-00000000-00011010-01101101 6765
00000000-00000000-00101010-11000010 10946
00000000-00000000-01000101-00101111 17711
00000000-00000000-01101111-11110001 28657
00000000-00000000-10110101-00100000 46368
00000000-00000001-00100101-00010001 75025
00000000-00000001-11011010-00110001 121393
00000000-00000010-11111111-01000010 196418
00000000-00000100-11011001-01110011 317811
00000000-00000111-11011000-10110101 514229
00000000-00001100-10110010-00101000 832040
00000000-00010100-10001010-11011101 1346269
00000000-00100001-00111101-00000101 2178309
00000000-00110101-11000111-11100010 3524578
00000000-01010111-00000100-11100111 5702887
00000000-10001100-11001100-11001001 9227465
00000000-11100011-11010001-10110000 14930352
00000001-01110000-10011110-01111001 24157817
00000010-01010100-01110000-00101001 39088169
00000011-11000101-00001110-10100010 63245986
00000110-00011001-01111110-11001011 102334155
00001001-11011110-10001101-01101101 165580141
00001111-11111000-00001100-00111000 267914296
00011001-11010110-10011001-10100101 433494437
00101001-11001110-10100101-11011101 701408733
01000011-10100101-00111111-10000010 1134903170

1bit 目は 1, 1, 0 の 3 拍子、 2bit 目は 0, 0, 1, 1, 0, 0 の 6/8 拍子、になっているようです。
下の桁の繰り上がりも影響しそうなものですが、 N bit 目についてそれぞれ 3 * N 倍周期の規則性が見えそうです。

ソースコード

上記二進数表示は、以下のコードで生成しました。 (long の代わりに long long を使えばもっと出せますね)

#include <stdio.h>

#define OCB(c) (c&1)|(c&2)<<2|(c&4)<<4|(c&8)<<6|(c&16)<<8|\
(c&32)<<10|(c&64)<<12|(c&128)<<14

int main() {
  long prev = 0, fib = 1;
  char *const pf = (void*) &fib;

  int loop = 45;
  while (loop --) {
    const long next = prev + fib;
    printf("%08o-%08o-%08o-%08o %ld\n",
           OCB(pf[3]), OCB(pf[2]), OCB(pf[1]), OCB(pf[0]), fib);
    prev = fib , fib = next;
  }

  return 0;
}

変更 2017.12.30
8 進数を媒介して都度計算するようにし、二進数変換テーブルを削除。