cp's OEIS Frontend

A020985 The Rudin-Shapiro or Golay-Rudin-Shapiro sequence (coefficients of the Shapiro polynomials).

%I A020985 #183 Jun 05 2025 10:04:19
%S A020985 1,1,1,-1,1,1,-1,1,1,1,1,-1,-1,-1,1,-1,1,1,1,-1,1,1,-1,1,-1,-1,-1,1,1,
%T A020985 1,-1,1,1,1,1,-1,1,1,-1,1,1,1,1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,1,-1,1,
%U A020985 1,1,-1,-1,-1,1,-1,1,1,1,-1,1,1,-1,1,1,1,1,-1,-1,-1,1,-1,1
%N A020985 The Rudin-Shapiro or Golay-Rudin-Shapiro sequence (coefficients of the Shapiro polynomials).
%C A020985 Other names are the Rudin-Shapiro or Golay-Rudin-Shapiro infinite word.
%C A020985 The Shapiro polynomials are defined by P_0 = Q_0 = 1; for n>=0, P_{n+1} = P_n + x^(2^n)*Q_n, Q_{n+1} = P_n - x^(2^n)*Q_n. Then P_n = Sum_{m=0..2^n-1} a(m)*x^m, where the a(m) (the present sequence) do not depend on n. - _N. J. A. Sloane_, Aug 12 2016
%C A020985 Related to paper-folding sequences - see the Mendès France and Tenenbaum article.
%C A020985 a(A022155(n)) = -1; a(A203463(n)) = 1. - _Reinhard Zumkeller_, Jan 02 2012
%C A020985 a(n) = 1 if and only if the numbers of 1's and runs of 1's in binary representation of n have the same parity: A010060(n) = A268411(n); otherwise, when A010060(n) = 1 - A268411(n), a(n) = -1. - _Vladimir Shevelev_, Feb 10 2016. Typo corrected and comment edited by _Antti Karttunen_, Jul 11 2017
%C A020985 A word that is uniform primitive morphic, but not pure morphic. - _N. J. A. Sloane_, Jul 14 2018
%C A020985 Named after the Austrian-American mathematician Walter Rudin (1921-2010), the mathematician Harold S. Shapiro (1928-2021) and the Swiss mathematician and physicist Marcel Jules Edouard Golay (1902-1989). - _Amiram Eldar_, Jun 13 2021
%D A020985 Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 78 and many other pages.
%H A020985 Reinhard Zumkeller, <a href="/A020985/b020985.txt">Table of n, a(n) for n = 0..10000</a>
%H A020985 Jean-Paul Allouche, <a href="http://ssdnm.mimuw.edu.pl/pliki/wyklady/allouche-uj.pdf">Lecture notes on automatic sequences</a>, Krakow October 2013.
%H A020985 Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and 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 A020985 Jean-Paul Allouche and M. Mendes France, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/allmendeshouches.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, Vol. 3, Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
%H A020985 Jean-Paul Allouche and M. Mendes France, <a href="/A003842/a003842.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
%H A020985 Jean-Paul Allouche and Jonathan Sondow, <a href="http://arxiv.org/abs/1408.5770">Summation of rational series twisted by strongly B-multiplicative coefficients</a>, arXiv:1408.5770 [math.NT], 2014; Electron. J. Combin., 22 #1 (2015) P1.59; see pp.9-10.
%H A020985 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.16.5 "The Golay-Rudin-Shapiro sequence", pp.44-45
%H A020985 Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H A020985 John Brillhart and L. Carlitz, <a href="https://doi.org/10.1090/S0002-9939-1970-0260955-6">Note on the Shapiro polynomials</a>, Proc. Amer. Math. Soc., Vol. 25 (1970), pp. 114-118.
%H A020985 John Brillhart and Patrick Morton, <a href="http://projecteuclid.org/euclid.ijm/1256048841">Über Summen von Rudin-Shapiroschen Koeffizienten</a>, (German) Illinois J. Math., Vol. 22, No. 1 (1978), pp. 126-148. MR0476686 (57 #16245). - From _N. J. A. Sloane_, Jun 06 2012
%H A020985 John Brillhart and Patrick 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, Vol. 103 (1996) pp. 854-869.
%H A020985 James D. Currie, Narad Rampersad, Kalle Saari, and Luca Q. Zamboni, <a href="http://arxiv.org/abs/1301.4972">Extremal words in morphic subshifts</a>, arXiv:1301.4972 [math.CO], 2013.
%H A020985 James D. Currie, Narad Rampersad, Kalle Saari, and Luca Q. Zamboni, <a href="http://dx.doi.org/10.1016/j.disc.2014.01.002">Extremal words in morphic subshifts</a>, Discrete Math., Vol. 322 (2014), pp. 53-60. MR3164037. See Sect. 8.
%H A020985 Michel Dekking, Michel Mendes France and Alf van der Poorten, <a href="https://doi.org/10.1007/BF03024244">Folds</a>, The Mathematical Intelligencer, Vol. 4, No. 3 (1982), pp. 130-138.
%H A020985 Michel Dekking, Michel Mendes France and Alf van der Poorten, <a href="https://doi.org/10.1007/BF03023552">Folds II. Symmetry disturbed</a>, The Mathematical Intelligencer, Vol. 4, No. 4 (1982), pp. 173-181.
%H A020985 Arturas Dubickas, <a href="http://dx.doi.org/10.4064/ap105-2-3">Heights of squares of Littlewood polynomials and infinite series</a>, Ann. Polon. Math., Vol. 105 (2012), pp. 145-163. - From _N. J. A. Sloane_, Dec 16 2012
%H A020985 Russell Jay Hendel, <a href="https://arxiv.org/abs/2505.20547">A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences</a>, arXiv:2505.20547 [cs.FL], 2025. See p. 2.
%H A020985 Albertus Hof, Oliver Knill and Barry Simon, <a href="http://inis.iaea.org/search/search.aspx?orig_q=RN:27016845">Singular continuous spectrum for palindromic Schroedinger operators</a>, Commun. Math. Phys., Vol. 174, No. 1 (1995), pp. 149-159.
%H A020985 Philip Lafrance, Narad Rampersad and Randy Yee, <a href="http://arxiv.org/abs/1408.2277">Some properties of a Rudin-Shapiro-like sequence</a>, arXiv:1408.2277 [math.CO], 2014.
%H A020985 D. H. Lehmer and Emma Lehmer, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002197537">Picturesque exponential sums. II</a>, Journal für die reine und angewandte Mathematik, Vol. 318 (1980), pp. 1-19.
%H A020985 Michel Mendès France and Gérald Tenenbaum, <a href="http://www.numdam.org/item?id=BSMF_1981__109__207_0">Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro</a>. (French) Bull. Soc. Math. France, Vol. 109, No. 2 (1981), pp. 207-215. MR0623789 (82k:10073).
%H A020985 Luke Schaeffer and Jeffrey Shallit, <a href="https://doi.org/10.37236/5752">Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences</a>, Electronic Journal of Combinatorics, Vol. 23, No. 1 (2016), #P1.25.
%H A020985 Harold S. Shapiro, <a href="http://hdl.handle.net/1721.1/12198">Extremal problems for polynomials and power series</a>, Ph.D. Diss. Massachusetts Institute of Technology, 1952.
%H A020985 Vladimir Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv:1603.04434 [math.NT], 2016.
%H A020985 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rudin-ShapiroSequence.html">Rudin-Shapiro Sequence</a>.
%F A020985 a(0) = a(1) = 1; thereafter, a(2n) = a(n), a(2n+1) = a(n) * (-1)^n. [Brillhart and Carlitz, in proof of theorem 4]
%F A020985 a(0) = a(1) = 1, a(2n) = a(n), a(2n+1) = a(n)*(1-2*(n AND 1)), where AND is the bitwise AND operator. - _Alex Ratushnyak_, May 13 2012
%F A020985 Brillhart and Morton (1978) list many properties.
%F A020985 a(n) = (-1)^A014081(n)  = (-1)^A020987(n) = 1-2*A020987(n). - _M. F. Hasler_, Jun 06 2012
%F A020985 Sum_{n >= 1} a(n-1)*(8*n^2+4*n+1)/(2*n*(2*n+1)*(4*n+1)) = 1; see Allouche and Sondow, 2015. - _Jean-Paul Allouche_ and _Jonathan Sondow_, Mar 21 2015
%p A020985 A020985 := proc(n) option remember; if n = 0 then 1 elif n mod 2 = 0 then A020985(n/2) else (-1)^((n-1)/2 )*A020985( (n-1)/2 ); fi; end;
%t A020985 a[0] = 1; a[1] = 1; a[n_?EvenQ] := a[n] = a[n/2]; a[n_?OddQ] := a[n] = (-1)^((n-1)/2)* a[(n-1)/2]; a /@ Range[0, 80] (* _Jean-François Alcover_, Jul 05 2011 *)
%t A020985 a[n_] := 1 - 2 Mod[Length[FixedPointList[BitAnd[#, # - 1] &, BitAnd[n, Quotient[n, 2]]]], 2] (* _Jan Mangaldan_, Jul 23 2015 *)
%t A020985 Array[RudinShapiro, 81, 0] (* _JungHwan Min_, Dec 22 2016 *)
%o A020985 (Haskell)
%o A020985 a020985 n = a020985_list !! n
%o A020985 a020985_list = 1 : 1 : f (tail a020985_list) (-1) where
%o A020985    f (x:xs) w = x : x*w : f xs (0 - w)
%o A020985 -- _Reinhard Zumkeller_, Jan 02 2012
%o A020985 (PARI) A020985(n)=(-1)^A014081(n)  \\ _M. F. Hasler_, Jun 06 2012
%o A020985 (Python)
%o A020985 def a014081(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)])
%o A020985 def a(n): return (-1)**a014081(n) # _Indranil Ghosh_, Jun 03 2017
%o A020985 (Python)
%o A020985 def A020985(n): return -1 if (n&(n>>1)).bit_count()&1 else 1 # _Chai Wah Wu_, Feb 11 2023
%Y A020985 Cf. A022155, A005943 (factor complexity), A014081.
%Y A020985 Cf. A020987 (0-1 version), A020986 (partial sums), A203531 (run lengths), A033999, A380667 (first differences).
%Y A020985 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 A020985 sign,nice,easy
%O A020985 0,1
%A A020985 _N. J. A. Sloane_