A036577 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.
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, 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, 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
Offset: 1
Keywords
Examples
2*x + x^2 + 2*x^4 + x^6 + 2*x^7 + x^8 + x^10 + 2*x^11 + 2*x^13 + x^14 + ...
References
- M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.
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.
- J. Berstel, Sur la construction de mots sans carré, Sém. Théor. Nombres Bordeaux (1978--1979), 18.01-18.15.
- F. Blanchet-Sadri, J. Currie, N. Fox, and N. Rampersad, Abelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1, INTEGERS 14 (2014), Paper A11.
- C. Braunholtz, Advanced problem 5030: An infinite sequence of three symbols with no adjacent repeats, Amer. Math. Monthly 70 (1963), 675--676.
- James D. Currie, Non-repetitive words: Ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 21.
- J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
- David Hamm and Jeffrey Shallit, Characterization of finite and one-sided infinite fixed points of morphisms on free monoids, Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999. See foot of page 2.
- S. Istrail, On irreductible languages and nonrational numbers, Bull. Math. Soc. Sci. Math. R. S. Roumanie 21 (1977), 301-308.
- Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
- Pierre Popoli, Jeffrey Shallit, and Manon Stipulanti, Additive word complexity and Walnut, arXiv:2410.02409 [math.CO], 2024. See p. 13.
- Michaël Rao, Michel Rigo, and Pavel Salimov, Avoiding 2-binomial squares and cubes, arXiv:1310.4743 [cs.FL], 2013.
- Michaël Rao, Michel Rigo, and Pavel Salimov, Avoiding 2-binomial squares and cubes, Theoretical Computer Science, Volume 572, 23 March 2015, Pages 83-91.
- Lukas Spiegelhofer, Gaps in the Thue-Morse word, arXiv:2102.01018 [math.CO], 2021.
Programs
-
Mathematica
(* 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 *) Nest[Flatten[# /. {2 -> {2, 1, 0}, 1 -> {2, 0}, 0 -> {1}}] &, {2, 1, 0}, 7] (* Robert G. Wilson v, Jul 30 2018 *) Differences[ThueMorse[Range[0, 100]]] + 1 (* Paolo Xausa, Jul 17 2025 *) -
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 */ -
Python
def A036577(n): return (n.bit_count()&1)+((n-1).bit_count()&1^1) # Chai Wah Wu, Mar 03 2023
Formula
a(n) = 3 - A007413(n). a(A036554(n)) = 1; a(A091785(n)) = 0; a(A091855(n)) = 2. - Philippe Deléham, Mar 20 2004
a(4*n + 2) = 1. a(2*n + 1) = 2 * A010059(n). a(4*n + 3) = 2 * A010060(n). - Michael Somos, Aug 03 2011
Comments