login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036577 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b. 18
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
Number of 1's between successive 0's in A010060.
The infinite sequence is abcacbabcbac... which is encoded with a->2, b->1, c->0 to produce this integer sequence.
From Jeffrey Shallit, Dec 07 2019: (Start)
This word is sometimes called 'vtm'; see, for example, see the Blanchet-Sadri et al. reference.
It is a squarefree word containing no instances of the factor 010 or 212 (or cbc, aba in the encoding).
Berstel proved many different definitions (e.g., Braunholtz, Istrail) of the word are equivalent. (End)
REFERENCES
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.
LINKS
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.
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.
FORMULA
a(n) = A036585(n) - 1 = A029883(n) + 1.
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
EXAMPLE
2*x + x^2 + 2*x^4 + x^6 + 2*x^7 + x^8 + x^10 + 2*x^11 + 2*x^13 + x^14 + ...
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 *)
PROG
(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
CROSSREFS
See A007413, A036580 for other versions.
Sequence in context: A321102 A368199 A091392 * A317189 A220136 A322454
KEYWORD
nonn
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:36 EDT 2024. Contains 371264 sequences. (Running on oeis4.)