Problem 384
Rudin-Shapiro sequence
Define the sequence a(n) as the number of adjacent pairs of ones in the binary expansion of n (possibly overlapping).
E.g.: a(5) = a(1012) = 0, a(6) = a(1102) = 1, a(7) = a(1112) = 2
Define the sequence b(n) = (-1)a(n).
This sequence is called the Rudin-Shapiro sequence.
Also consider the summatory sequence of b(n): $s(n)=\sum_{i=0}^{n}b(i)$.
The first couple of values of these sequences are:
| 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 |
The sequence s(n) has the remarkable property that all elements are positive and every positive integer k occurs exactly k times.
Define g(t,c), with 1 ≤ c ≤ t, as the index in s(n) for which t occurs for the c’th time in s(n).
E.g.: g(3,3) = 6, g(4,2) = 7 and g(54321,12345) = 1220847710.
Let F(n) be the fibonacci sequence defined by:
F(0)=F(1)=1 and
F(n)=F(n-1)+F(n-2) for n>1.
Define GF(t)=g(F(t),F(t-1)).
Find ΣGF(t) for 2≤t≤45.
鲁丁-夏皮罗序列
定义序列a(n)为在n的二进制表示中两个1相邻出现的次数（可能有重叠）。
例如：a(5) = a(1012) = 0，a(6) = a(1102) = 1，a(7) = a(1112) = 2
定义序列b(n) = (-1)a(n)。
这个序列被称为鲁丁-夏皮罗序列。
同时，考虑b(n)的部分和序列：$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次。
定义g(t,c)为t在s(n)中第c次出现时的下标，其中1 ≤ c ≤ t。
例如：g(3,3) = 6，g(4,2) = 7以及g(54321,12345) = 1220847710。
令F(n)表示斐波那契数列，按如下方式定义：
F(0)=F(1)=1 且
对于n>1，F(n)=F(n-1)+F(n-2)。
定义GF(t)=g(F(t),F(t-1))。
对于2≤t≤45，求ΣGF(t)。