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

$n$を二進展開したものに存在する1の隣接ペアの個数を表す数列$a(n)$を定義しよう(隣接ペアは7の場合のように重なりがある可能性がある)。 例えば、$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)}$と定義しよう。 この数列はルーディン-シャピロ数列(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)$と表すと定義しよう。 例えば$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)$を求めよ。