# 384 : ルーディン-シャピロ数列

$$n$$を二進展開したものに存在する1の隣接ペアの個数を表す数列$$a(n)$$を定義しよう(隣接ペアは7の場合のように重なりがある可能性がある)。\
&#x20;例えば、$$a(5) = a(101_2) = 0, a(6) = a(110_2) = 1, a(7) = a(111_2) = 2$$となる。

数列$$b(n)$$を$$b(n) = (-1)^{a(n)}$$と定義しよう。\
&#x20;この数列は**ルーディン-シャピロ**数列(Rudin-Shapiro sequence)と呼ばれる。

$$b(n)$$を順次総和してできる数列(summatory sequence)$$s(n) = \sum_{i=0}^n b(i)$$を考えよう。

これらの数列の最初の値は以下のようになる。

| n    | 0 | 1 | 2 | 3  | 4 | 5 | 6  | 7 |
| ---- | - | - | - | -- | - | - | -- | - |
| a(n) | 0 | 0 | 0 | 1  | 0 | 0 | 1  | 2 |
| b(n) | 1 | 1 | 1 | -1 | 1 | 1 | -1 | 1 |
| s(n) | 1 | 2 | 3 | 2  | 3 | 4 | 3  | 4 |

数列$$s(n)$$はすべての要素が正の整数となり, さらにその整数$$k$$はちょうど$$k$$回現れるという注目すべき性質を持っている。

数列$$s(n)$$に$$t$$が$$c$$回目に現れたときの$$s(n)$$における添字を、$$1 \leq c \leq t$$のとき$$g(t,c)$$と表すと定義しよう。\
&#x20;例えば$$g(3,3) = 6, g(4,2) = 7, g(54321,12345) = 1220847710$$となる。

$$F(n)$$を以下のように定義されるフィボナッチ数列としよう。\
$$F(0)=F(1)=1$$\
$$F(n)=F(n-1)+F(n-2)$$（$$n>1$$のとき）

$$GF(t)=g(F(t),F(t-1))$$と定義しよう。

$$2 ≤ t ≤ 45$$に対する$$\sum GF(t)$$を求めよ。
