A029883 First differences of Thue-Morse sequence A001285.

1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, 0, -1

Offset: 1

Author

N. J. A. Sloane, Dec 11 1999

Keywords

• sign
• easy

Comments

Also first differences of {0,1} Thue-Morse sequence A010060.- N. J. A. Sloane, Jan 05 2021

Fixed point of the morphism a->abc, b->ac, c->b, with a = 1, b = 0, c = -1, starting with a(1) = 1. - Philippe Deléham

From Thomas Anton, Sep 22 2020: (Start)

This sequence, interpreted as an infinite word, is squarefree.

Let & represent concatenation. For a word w of integers, let -w be the same word with each symbol negated. Then, starting with the empty word, this sequence can be obtained by iteratively applying the transformation T(w) = w & 1 & -w & 0 & -w & -1 & w. (End)

Links

• G. C. Greubel, Table of n, a(n) for n = 1..10000
• J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
• G. N. Arzhantseva, C. H. Cashen, D. Gruber, and D. Hume, Contracting geodesics in infinitely presented graphical small cancellation groups, arXiv preprint arXiv:1602.03767 [math.GR], 2016-2017.
• T. W. Cusick, H. Fredricksen and P. Stănică, On the delta sequence of the Thue-Morse sequence, Australas. J. Combin. 39 (2007), 293--300. [From _N. J. A. Sloane_, Dec 11 2009]
• Florian Frohn and Jürgen Giesl, Proving Non-Termination by Acceleration Driven Clause Learning with LoAT, arXiv:2304.10166 [cs.LO], 2023.
• Index entries for sequences that are fixed points of mappings

Crossrefs

Apart from signs, same as A035263. Cf. A001285, A010060, A036554, A091785, A091855.

a(n+1) = A036577(n) - 1 = A036585(n) - 2.

Programs

Mathematica

Nest[ Function[ l, {Flatten[(l /. {0 -> {1, -1}, 1 -> {1, 0, -1}, -1 -> {0}})]}], {1}, 7] (* Robert G. Wilson v, Feb 26 2005 *)
ThueMorse /@ Range[0, 105] // Differences (* Jean-François Alcover, Oct 15 2019 *)

PARI

a(n)=if(n<1||valuation(n,2)%2,0,-(-1)^subst(Pol(binary(n)),x,1)) /* Michael Somos, Jul 08 2004 */

PARI

a(n)=hammingweight(n)%2-hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 26 2013

Python

def A029883(n): return (bin(n).count('1')&1)-(bin(n-1).count('1')&1) # Chai Wah Wu, Mar 03 2023

Formula

Recurrence: a(4*n) = a(n), a(4*n+1) = a(2*n+1), a(4*n+2) = 0, a(4*n+3) = -a(2*n+1), starting a(1) = 1.

a(n) = 2 - A007413(n). a(A036554(n)) = 0; a(A091785(n)) = -1; a(A091855(n)) = 1. - Philippe Deléham, Mar 20 2004

G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = -v+w+u^2-v^2+2*w^2-2*u*w. - Michael Somos, Jul 08 2004

Extensions

Edited by Ralf Stephan, Dec 09 2004