The Rudin-Shapiro sequence is a sequence of signs encoding the parity of the number of occurrences of 11 in binary
expansions. Let an integer 
be written in binary as
 |
(1)
|
where 
and each 
is 0 or 1. Define
 |
(2)
|
as the number of overlapping digit blocks of 11 in the binary expansion of 
, with the empty sum equal to 0 when 
. For 
, 1, ..., 
is given by 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2,
3, ... (OEIS A014081).
Now define
 |
(3)
|
as the sign encoding this parity: 
when 
is even and 
when 
is odd. For 
, 1, ..., the first few values are 1, 1, 1, -1, 1, 1, -1,
1, 1, 1, 1, -1, -1, -1, ... (OEIS A020985).
The sequence is also known as the Golay-Rudin-Shapiro sequence.
The summatory sequence of 
is then defined by
 |
(4)
|
giving the first few terms for 
, 1, ... as 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, ...
(OEIS A020986).
Each positive integer 
occurs exactly 
times in the summatory sequence
(Brillhart and Morton 1978), and its positions are given by the number triangle
 |
(5)
|
(OEIS A093573).
For the special case 
with 
, 
can be computed using the formula
 |
(6)
|
(Blecksmith and Laud 1995), giving for 
, 2, ... the values 2, 3, 3, 5, 5, 9, 9, 17, 17, 33, 33,
65, ... (OEIS A051032). This sequence is therefore
pairs of terms of the sequence 2, 3, 5, 9, 17, ... (OEIS A000051;
keeping only a single member of the initial term), i.e., numbers of the form 
for 
,
1, ....
