login
First differences of Thue-Morse sequence A001285.
12

%I #67 Jul 19 2024 03:10:15

%S 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,

%T 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,

%U -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

%N First differences of Thue-Morse sequence A001285.

%C Also first differences of {0,1} Thue-Morse sequence A010060.- _N. J. A. Sloane_, Jan 05 2021

%C 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_

%C From _Thomas Anton_, Sep 22 2020: (Start)

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

%C 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)

%H G. C. Greubel, <a href="/A029883/b029883.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche and Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/ubiq15.pdf">The Ubiquitous Prouhet-Thue-Morse Sequence</a>, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.

%H G. N. Arzhantseva, C. H. Cashen, D. Gruber, and D. Hume, <a href="http://arxiv.org/abs/1602.03767">Contracting geodesics in infinitely presented graphical small cancellation groups</a>, arXiv preprint arXiv:1602.03767 [math.GR], 2016-2017.

%H T. W. Cusick, H. Fredricksen and P. Stănică, <a href="http://ajc.maths.uq.edu.au/pdf/39/ajc_v39_p293.pdf">On the delta sequence of the Thue-Morse sequence</a>, Australas. J. Combin. 39 (2007), 293--300. [From _N. J. A. Sloane_, Dec 11 2009]

%H Florian Frohn and Jürgen Giesl, <a href="https://arxiv.org/abs/2304.10166">Proving Non-Termination by Acceleration Driven Clause Learning with LoAT</a>, arXiv:2304.10166 [cs.LO], 2023.

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%F 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.

%F a(n) = 2 - A007413(n). a(A036554(n)) = 0; a(A091785(n)) = -1; a(A091855(n)) = 1. - _Philippe Deléham_, Mar 20 2004

%F 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

%t Nest[ Function[ l, {Flatten[(l /. {0 -> {1, -1}, 1 -> {1, 0, -1}, -1 -> {0}})]}], {1}, 7] (* _Robert G. Wilson v_, Feb 26 2005 *)

%t ThueMorse /@ Range[0, 105] // Differences (* _Jean-François Alcover_, Oct 15 2019 *)

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

%o (PARI) a(n)=hammingweight(n)%2-hammingweight(n-1)%2 \\ _Charles R Greathouse IV_, Mar 26 2013

%o (Python)

%o def A029883(n): return (bin(n).count('1')&1)-(bin(n-1).count('1')&1) # _Chai Wah Wu_, Mar 03 2023

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

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

%K sign,easy

%O 1,1

%A _N. J. A. Sloane_, Dec 11 1999

%E Edited by _Ralf Stephan_, Dec 09 2004