## 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:

$(\text{prime}-k)$ FactorialGenerating Polygons

Divisibility Comparison Between Factorials