1が連続しない2進数の数とフィボナッチ数列の関係

以下のような例題を解くことを考えます。

例題. $n\leqq2^{20}$で、2進数表記したとき１が連続しない自然数nの数を答えよ

2進数表記したとき１が連続しないということは、1ビットシフト（2倍）して論理積(&)を取ると0になるということなので。4桁まで求めると以下のように7個になります。

for n in range(1,2**4):
  if n&(2*n) == 0:
    print(f"{n:3} | {n: >10b}")
#  1 |          1
#  2 |         10
#  4 |        100
#  5 |        101
#  8 |       1000
#  9 |       1001
# 10 |       1010

さらに5桁目まで求めて各桁ごとの数を見てみると、1,1,2,3,5,...となりこれはフィボナッチ数列？と思わせます。そこでよく見てみると5桁の最初の3つは4桁の数から、後の2つは3桁の数から作られています。

  n |  桁数|   2進数
-----------------------
  1 |    1 |         1
-----------------------
  2 |    2 |        10
-----------------------
  4 |    3 |       100 |--------------------+
  5 |    3 |       101 |                    |
-----------------------                     | 左に
  8 |    4 |      1000 |                    | 10をつける
  9 |    4 |      1001 | --+                |
 10 |    4 |      1010 |   |                |
-----------------------    | 左の1を取って  |
 16 |    5 |     10000 +   | 10をつける     |
 17 |    5 |     10001 |<--+　              | 
 18 |    5 |     10010 +                    |
 20 |    5 |     10100 +<-------------------+
 21 |    5 |     10101 |

元の例題にもどって、最初のループで$2^{20}$まで走らせてカウントすると$17710$となり、
フィボナッチ数列の$2^{20}$までの和は以下の公式によりK=20のとき$F(22)-1=17710$と一致します。最終的な答えは$2^{20}$自身を加えて$17711$となります。

$\large \sum_{k=1}^{n}F(k) = F(n+2)-1$

$n=2^{20}$程度では時間にあまり差はでませんが$2^{30}$くらいを超えてくると以下のリンクで紹介した方法等でフィボナッチ数列を計算した方が格段に速くなります。

フィボナッチ数列を行列を使ってO(log(n))で計算する

この考え方はProuect Euler: Problem 301等を考えるときに役に立つかもしれません。

（開発環境：Google Colab）