|
|
A020985
|
|
The Rudin-Shapiro or Golay-Rudin-Shapiro sequence (coefficients of the Shapiro polynomials).
|
|
53
|
|
|
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, 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, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
Other names are the Rudin-Shapiro or Golay-Rudin-Shapiro infinite word.
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
Related to paper-folding sequences - see the Mendès France and Tenenbaum article.
A word that is uniform primitive morphic, but not pure morphic. - N. J. A. Sloane, Jul 14 2018
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
|
|
REFERENCES
|
Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 78 and many other pages.
|
|
LINKS
|
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017
Jean-Paul Allouche and M. Mendes France, Automata and Automatic Sequences, 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.
Jean-Paul Allouche and M. Mendes France, Automata and Automatic Sequences, 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]
Michel Dekking, Michel Mendes France and Alf van der Poorten, Folds, The Mathematical Intelligencer, Vol. 4, No. 3 (1982), pp. 130-138.
Michel Dekking, Michel Mendes France and Alf van der Poorten, Folds II. Symmetry disturbed, The Mathematical Intelligencer, Vol. 4, No. 4 (1982), pp. 173-181.
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics, Vol. 23, No. 1 (2016), #P1.25.
|
|
FORMULA
|
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]
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
Brillhart and Morton (1978) list many properties.
|
|
MAPLE
|
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;
|
|
MATHEMATICA
|
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 *)
a[n_] := 1 - 2 Mod[Length[FixedPointList[BitAnd[#, # - 1] &, BitAnd[n, Quotient[n, 2]]]], 2] (* Jan Mangaldan, Jul 23 2015 *)
|
|
PROG
|
(Haskell)
a020985 n = a020985_list !! n
a020985_list = 1 : 1 : f (tail a020985_list) (-1) where
f (x:xs) w = x : x*w : f xs (0 - w)
(Python)
def a014081(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)])
(Python)
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
sign,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|