login
Zero-one version of Golay-Rudin-Shapiro sequence (or word).
32

%I #70 Feb 12 2023 03:06:48

%S 0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,0,1,1,1,0,0,0,1,0,0,0,

%T 0,1,0,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,1,1,0,1,0,0,0,1,1,1,0,1,0,0,0,1,

%U 0,0,1,0,0,0,0,1,1,1,0,1,0

%N Zero-one version of Golay-Rudin-Shapiro sequence (or word).

%C This is (1-A020985(n))/2. See A020985, which is the main entry for this sequence, for more information. _N. J. A. Sloane_, Jun 06 2012

%C A word that is uniform primitive morphic, but not pure morphic. - _N. J. A. Sloane_, Jul 14 2018

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 78.

%D Dekking, Michel, Michel Mendes France, and Alf van der Poorten. "Folds." The Mathematical Intelligencer, 4.3 (1982): 130-138 & front cover, and 4:4 (1982): 173-181 (printed in two parts).

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

%D Lipshitz, Leonard, and A. van der Poorten. "Rational functions, diagonals, automata and arithmetic." In Number Theory, Richard A. Mollin, ed., Walter de Gruyter, Berlin (1990): 339-358.

%H Reinhard Zumkeller, <a href="/A020987/b020987.txt">Table of n, a(n) for n = 0..10000</a>

%H Jean-Paul Allouche, <a href="https://doi.org/10.1063/1.531916">Schrödinger Operators with Rudin-Shapiro Potentials are not Palindromic</a>, Journal of Mathematical Physics, volume 38, number 4, 1997, pages 1843-1848. And <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/allouche97c.ps">the author's copy</a>. Section IV v_n = a(n) for the Rudin-Shapiro case given there i_0 = 0 and otherwise i_m = m+1 mod 2.

%H Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, Luca Q. Zamboni, <a href="https://arxiv.org/abs/1711.10807">A Taxonomy of Morphic Sequences</a>, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017

%H J. Brillhart and P. Morton, <a href="http://www.maa.org/programs/maa-awards/writing-awards/a-case-study-in-mathematical-research-the-golay-rudin-shapiro-sequence">A case study in mathematical research: the Golay-Rudin-Shapiro sequence</a>, Amer. Math. Monthly, 103 (1996) 854-869.

%H James D. Currie, Narad Rampersad, Kalle Saari, Luca Q. Zamboni, <a href="http://dx.doi.org/10.1016/j.disc.2014.01.002">Extremal words in morphic subshifts</a>, Discrete Math. 322 (2014), 53--60. MR3164037. See Sect. 8.

%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>

%H A. Hof, O. Knill and B. Simon, <a href="http://projecteuclid.org/euclid.cmp/1104275098">Singular continuous spectrum for palindromic Schroedinger operators</a>, Commun. Math. Phys. 174 (1995), 149-159.

%H L. Lipshitz and A. J. van der Poorten, <a href="http://www-centre.mpce.mq.edu.au/alfpapers/a084.pdf">Rational functions, diagonals, automata and arithmetic</a>

%H H. Niederreiter and M. Vielhaber, <a href="http://dx.doi.org/10.1006/jcom.1996.0014">Tree complexity and a doubly exponential gap between structured and random sequences</a>, J. Complexity, 12 (1996), 187-198.

%H Aayush Rajasekaran, Narad Rampersad, Jeffrey Shallit, <a href="https://dx.doi.org/10.1007/978-3-319-66396-8_3">Overpals, Underlaps, and Underpals</a>, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.

%H Thomas Stoll, <a href="https://hal.archives-ouvertes.fr/hal-01278708">On digital blocks of polynomial values and extractions in the Rudin-Shapiro sequence</a>, RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2016, 50, pp. 93-99. <hal-01278708>.

%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>

%t a[n_] := (1/2)*(1-(-1)^Count[Partition[IntegerDigits[n, 2], 2, 1], {1, 1}]); Table[a[n], {n, 0, 80}] (* _Jean-François Alcover_, Dec 12 2014, after _Robert G. Wilson v_ *)

%o (Haskell)

%o a020987 = (`div` 2) . (1 -) . a020985 -- _Reinhard Zumkeller_, Jun 06 2012

%o (Python)

%o def A020987(n): return (n&(n>>1)).bit_count()&1 # _Chai Wah Wu_, Feb 11 2023

%Y Cf. A020985.

%Y A014081(n) mod 2. Characteristic function of A022155.

%Y Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.

%K nonn,nice

%O 0,1

%A _N. J. A. Sloane_