Rudin-Shapiro Sequence

Author

Eric W. Weisstein
December 20, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/Rudin-ShapiroSequence.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Rudin-ShapiroSequence.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Definition

Blocks of 11

BlocksOf11[n_]:=Count[Partition[IntegerDigits[n,2],2,1],{1,1}]

b=BlocksOf11/@Range[0,128]

a=(-1)^#&/@b

s=Rest[FoldList[Plus,0,a]]

Binary Plot

<<Utilities`Plot`

s=Rest[FoldList[Plus,0,(-1)^#&/@BlocksOf11/@Range[0,255]]];

Show[PixelPerfect[NaryPlot[s],BlockSize->2]]

The Number n Occurs n Times

s=Rest[FoldList[Plus,0,(-1)^#&/@BlocksOf11/@Range[0,1024]]];

Through[{First,Length}[#]]&/@Split[Sort[Take[s,512]]]

Positions of 1, 2, 3, …

Sort[MapIndexed[Prepend[#2,#1]&,Take[s,100]]]

Last/@Sort[MapIndexed[Prepend[#2,#1]&,Take[s,100]]]-1

Special Case

ss[k_]:=If[EvenQ[k],2^(k/2)+1,2^((k-1)/2)+1]

Table[s[[2^(k-1)+1]],{k,8}]

pairs=Partition[Rest[ss/@Range[100]],2]

And@@Equal@@@pairs

First/@pairs