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(101_2) = 0$, $a(6) = a(110_2) = 1$, $a(7) = a(111_2) = 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 \limits_{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 \le c \le 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 \gt 1$.
Define $GF(t)=g(F(t),F(t-1))$.
Find $\sum GF(t)$ for $2 \le t \le 45$.

Given the problem’s complexity, it’s not practical to calculate each term of the sequences by brute force. This is where number theory comes to rescue. We need to find a pattern or a shortcut to save computations. Note that the sequence $a(n)$ is actually closely related to the Thue-Morse sequence, a binary sequence that is generated by iteratively appending the bitwise negation of a given sequence starting with 0.

First, we observe that calculating the term $b(n)$ depends on the parity of the number of 1-pairs in the binary representation of $n$. Here’s an important hint: if we write out the terms of $a(n)$ in binary form for n from 0 to 15, a pattern begins to emerge:

0 – 0000
1 – 0001
2 – 0010
3 – 0011
4 – 0100
5 – 0101
6 – 0110
7 – 0111
8 – 1000
9 – 1001
10 – 1010
11 – 1011
12 – 1100
13 – 1101
14 – 1110
15 – 1111

$a(n)$ sequence is:
0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 1, 0, 0, 1, 2.

Notice something? Besides the special case of n=0, the binary representations are partitioned into 2s with matching a(n) values. In effect, we can say a(n) = a(n/4) + a(n mod 4) for n greater than or equal 4.

Using this pattern, we can significantly speed up computation of $b(n)$ and in turn $s(n)$.

An optimized way to compute $s(n)$, would be to use the inherent structure of the Thue-Morse related sequence. Rather than calculating the sum for each $n$, manipulations could be made in an algorithmic fashion to get to $g(t, c)$ directly.

For $GF(t)$, since it involves the Fibonacci sequence, each term depends only on the past two terms. We could use the simple iterative method or matrix exponentiation to compute each term of $GF(t)$ quickly.

Finally, adding each term of GF(t) for $2 \le t \le 45$ gives us the desired summation.

Given the problem’s complexity and the vast range of techniques required to solve it, it’d be more suitable for a computer programming language to aid in the calculations. Python, Java, C++, or similar languages would be helpful for implementing the above strategies.

More Answers: