TOPICS
Search

Rudin-Shapiro Sequence


Let a number n be written in binary as

 n=(epsilon_kepsilon_(k-1)...epsilon_1epsilon_0)_2,
(1)

and define

 b_n=sum_(i=0)^(k-1)epsilon_iepsilon_(i+1)
(2)

as the number of digits blocks of 11s in the binary expansion of n. For n=0, 1, ..., b_n is given by 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (OEIS A014081).

Now define

 a_n=(-1)^(b_n)
(3)

as the parity of the number of pairs of consecutive 1s in the binary expansion of n. For n=0, 1, ..., the first few values are 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, ... (OEIS A020985). This is known as the Rudin-Shapiro, or sometimes Golay-Rudin-Shapiro sequence.

Binary plot of the Rudin-Shapiro sequence

The summatory sequence of a_n is then defined by

 s_n=sum_(i=0)^na_i,
(4)

giving the first few terms for n=0, 1, ... as 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, ... (OEIS A020986).

Interestingly, the positive integer n occurs exactly n times in the sequence, and the positions of n in sequence are given by the number triangle

 0 
1,3 
2,4,6 
5,7,13,15 
8,12,14,16,26
(5)

(OEIS A093573).

For the special case n=2^(k-1), s_n can be computed using the formula

 s_n={2^(k/2)+1   if k is even; 2^((k-1)/2)+1   if k is odd
(6)

(Blecksmith and Laud 1995), giving for n=1, 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 2^n+1.


See also

Binary, Digit Block, Folding, Stolarsky-Harborth Constant

Explore with Wolfram|Alpha

References

Allouche, J.-P. and Shallit, J. "Example 5.1.5 (The Rudin-Shapiro Sequence)." Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 78-80 and 154-155, 2003.Blecksmith, R. and Laud, P. W. "Some Exact Number Theory Computations via Probability Mechanisms." Amer. Math. Monthly 102, 893-903, 1995.Brillhart, J.; Erdős, P.; and Morton, P. "On the Sums of the Rudin-Shapiro Coefficients II." Pac. J. Math. 107, 39-69, 1983.Brillhart, J. and Morton, P. "Über Summen von Rudin-Shapiroschen Koeffizienten." Ill. J. Math. 22, 126-148, 1978.Mendes France, M. and van der Poorten, A. J. "Arithmetic and Analytic Properties of Paper Folding Sequences." Bull. Austral. Math. Soc. 24, 123-131, 1981.Sloane, N. J. A. Sequences A000051/M0717, A014081, A020985, A020986, A051032, and A093573 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Rudin-Shapiro Sequence

Cite this as:

Weisstein, Eric W. "Rudin-Shapiro Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Rudin-ShapiroSequence.html

Subject classifications