A036577 - OEIS

%I #71 Oct 24 2024 14:56:37

%S 2,1,0,2,0,1,2,1,0,1,2,0,2,1,0,2,0,1,2,0,2,1,0,1,2,1,0,2,0,1,2,1,0,1,

%T 2,0,2,1,0,1,2,1,0,2,0,1,2,0,2,1,0,2,0,1,2,1,0,1,2,0,2,1,0,2,0,1,2,0,

%U 2,1,0,1,2,1,0,2,0,1,2,0,2,1,0,2,0,1,2,1,0,1,2,0,2,1,0,1,2,1,0,2,0,1,2,1,0

%N Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.

%C Number of 1's between successive 0's in A010060.

%C The infinite sequence is abcacbabcbac... which is encoded with a->2, b->1, c->0 to produce this integer sequence.

%C From _Jeffrey Shallit_, Dec 07 2019: (Start)

%C This word is sometimes called 'vtm'; see, for example, see the Blanchet-Sadri et al. reference.

%C It is a squarefree word containing no instances of the factor 010 or 212 (or cbc, aba in the encoding).

%C Berstel proved many different definitions (e.g., Braunholtz, Istrail) of the word are equivalent. (End)

%D M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.

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

%H J.-P. Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps">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 J. Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1979SeminaireBordeaux.pdf">Sur la construction de mots sans carré</a>, Sém. Théor. Nombres Bordeaux (1978--1979), 18.01-18.15.

%H F. Blanchet-Sadri, J. Currie, N. Fox, and N. Rampersad, <a href="http://math.colgate.edu/~integers/o11/o11.Abstract.html">Abelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1</a>, INTEGERS 14 (2014), Paper A11.

%H C. Braunholtz, <a href="https://www.jstor.org/stable/2311652">Advanced problem 5030: An infinite sequence of three symbols with no adjacent repeats</a>, Amer. Math. Monthly 70 (1963), 675--676.

%H James D. Currie, <a href="https://doi.org/10.1007/BF01300125">Non-repetitive words: Ages and essences</a>, Combinatorica 16.1 (1996): 19-40. See p. 21.

%H J. Grytczuk, <a href="http://dx.doi.org/10.1016/j.disc.2007.08.039">Thue type problems for graphs, points and numbers</a>, Discrete Math., 308 (2008), 4419-4429.

%H David Hamm and Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/hamm2.ps">Characterization of finite and one-sided infinite fixed points of morphisms on free monoids</a>, Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999. See foot of page 2.

%H S. Istrail, <a href="https://www.jstor.org/stable/43759446">On irreductible languages and nonrational numbers</a>, Bull. Math. Soc. Sci. Math. R. S. Roumanie 21 (1977), 301-308.

%H Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, <a href="https://arxiv.org/abs/2207.10171">Pseudoperiodic Words and a Question of Shevelev</a>, arXiv:2207.10171 [math.CO], 2022.

%H Pierre Popoli, Jeffrey Shallit, and Manon Stipulanti, <a href="https://arxiv.org/abs/2410.02409">Additive word complexity and Walnut</a>, arXiv:2410.02409 [math.CO], 2024. See p. 13.

%H Michaël Rao, Michel Rigo, and Pavel Salimov, <a href="https://arxiv.org/abs/1310.4743">Avoiding 2-binomial squares and cubes</a>, arXiv:1310.4743 [cs.FL], 2013.

%H Michaël Rao, Michel Rigo, and Pavel Salimov, <a href="https://doi.org/10.1016/j.tcs.2015.01.029">Avoiding 2-binomial squares and cubes</a>, Theoretical Computer Science, Volume 572, 23 March 2015, Pages 83-91.

%H Lukas Spiegelhofer, <a href="https://arxiv.org/abs/2102.01018">Gaps in the Thue-Morse word</a>, arXiv:2102.01018 [math.CO], 2021.

%F a(n) = A036585(n) - 1 = A029883(n) + 1.

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

%F a(4*n + 2) = 1. a(2*n + 1) = 2 * A010059(n). a(4*n + 3) = 2 * A010060(n). - _Michael Somos_, Aug 03 2011

%e 2*x + x^2 + 2*x^4 + x^6 + 2*x^7 + x^8 + x^10 + 2*x^11 + 2*x^13 + x^14 + ...

%t (* ThueMorse is built-in since version 10.2, for lower versions it needs to be defined manually *) ThueMorse[n_] := Mod[DigitCount[n, 2, 1], 2]; Table[1 + ThueMorse[n] - ThueMorse[n-1], {n, 1, 100}]  (* _Vladimir Reshetnikov_, May 17 2016 *)

%t Nest[Flatten[# /. {2 -> {2, 1, 0}, 1 -> {2, 0}, 0 -> {1}}] &, {2, 1, 0}, 7] (* _Robert G. Wilson v_, Jul 30 2018 *)

%o (PARI) {a(n) = if( n<1, 0, if( valuation( n, 2)%2, 1, 1 - (-1)^subst( Pol( binary(n)), x, 1)))} /* _Michael Somos_, Aug 03 2011 */

%o (Python)

%o def A036577(n): return (n.bit_count()&1)+((n-1).bit_count()&1^1) # _Chai Wah Wu_, Mar 03 2023

%Y Cf. A010059, A010060, A029883, A036585, A104248.

%Y See A007413, A036580 for other versions.

%K nonn

%O 1,1

%A _N. J. A. Sloane_