|
| |
|
|
A020985
|
|
The Rudin-Shapiro or Golay-Rudin-Shapiro sequence (coefficients of the Shapiro polynomials).
|
|
14
|
|
|
|
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(A022155(n)) = -1; a(A203463(n)) = 1. - Reinhard Zumkeller, Jan 02 2012
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
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 78 and many other pages.
|
|
|
LINKS
|
Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J.-P. Allouche, Lecture notes on automatic sequences, Krakow October 2013.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences.
Jean-Paul Allouche and Jonathan Sondow, Summation of rational series twisted by strongly B-multiplicative coefficients, arXiv:1408.5770 [math.NT], 2014; Electron. J. Combin., 22 #1 (2015) P1.59; see pp.9-10.
Joerg Arndt, Matters Computational (The Fxtbook), section 1.16.5 "The Golay-Rudin-Shapiro sequence", pp.44-45
J. Brillhart and L. Carlitz, Note on the Shapiro polynomials, Proc. Amer. Math. Soc. 25 (1970), 114-118.
John Brillhart, Patrick Morton, Über Summen von Rudin-Shapiroschen Koeffizienten, (German) Illinois J. Math. 22 (1978), no. 1, 126--148. MR0476686 (57 #16245). - From N. J. A. Sloane, Jun 06 2012
John Brillhart and Patrick Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869.
James D. Currie, Narad Rampersad, Kalle Saari, Luca Q. Zamboni, Extremal words in morphic subshifts, arXiv:1301.4972 [math.CO], 2013.
James D. Currie, Narad Rampersad, Kalle Saari, Luca Q. Zamboni, Extremal words in morphic subshifts, Discrete Math. 322 (2014), 53--60. MR3164037. See Sect. 8.
Arturas Dubickas, Heights of squares of Littlewood polynomials and infinite series, Ann. Polon. Math. 105 (2012), 145-163. - From N. J. A. Sloane, Dec 16 2012
A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
Philip Lafrance, Narad Rampersad, Randy Yee, Some properties of a Rudin-Shapiro-like sequence, arXiv:1408.2277 [math.CO], 2014.
D. H. Lehmer, and Emma Lehmer, Picturesque exponential sums. II, Journal für die reine und angewandte Mathematik, 318 (1980), 1-19.
Mendès France, M.; Tenenbaum, G. Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro. (French) Bull. Soc. Math. France 109 (1981), no. 2, 207--215. MR0623789 (82k:10073).
Luke Schaeffer, Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
Harold S. Shapiro, Extremal problems for polynomials and power series, Ph.D. Diss. Massachusetts Institute of Technology, 1952.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016.
Eric Weisstein's World of Mathematics, Rudin-Shapiro Sequence
|
|
|
FORMULA
|
a(0) = 1, a(2n) = a(n), a(2n+1) = a(n) * (-1)^n.
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.
a(n) = (-1)^A014081(n) = (-1)^A020987(n) = 1-2*A020987(n). - M. F. Hasler, Jun 06 2012
Sum(n >= 1, a(n-1)(8n^2+4n+1)/2n(2n+1)(4n+1)) = 1; see Allouche and Sondow, 2015. - Jean-Paul Allouche and Jonathan Sondow, Mar 21 2015
|
|
|
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 *)
Array[RudinShapiro, 81, 0] (* JungHwan Min, Dec 22 2016 *)
|
|
|
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)
-- Reinhard Zumkeller, Jan 02 2012
(PARI) A020985(n)=(-1)^A014081(n) \\ M. F. Hasler, Jun 06 2012
(Python)
def a014081(n): return sum([((n>>i)&3==3) for i in xrange(len(bin(n)[2:]) - 1)])
def a(n): return (-1)**a014081(n) # Indranil Ghosh, Jun 03 2017
|
|
|
CROSSREFS
|
Cf. A022155, A005943, A014081.
Cf. A020987 (0-1 version), A020986 (partial sums), A203531 (run lengths), A033999.
Sequence in context: A108784 * A034947 A097807 A014077 A174351 A181432
Adjacent sequences: A020982 A020983 A020984 * A020986 A020987 A020988
|
|
|
KEYWORD
|
sign,nice,easy,changed
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
STATUS
|
approved
|
| |
|
|
