login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 17
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

James D. Currie, Non-repetitive words: ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 21.

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.

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.

Michaël Rao, Michel Rigo, Pavel Salimov, Avoiding 2-binomial squares and cubes, arXiv:1310.4743 [cs.FL], 2013.

Michaël Rao, Michel Rigo, 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 */

CROSSREFS

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

See A007413, A036580 for other versions.

Sequence in context: A298731 A321102 A091392 * A317189 A220136 A322454

Adjacent sequences:  A036574 A036575 A036576 * A036578 A036579 A036580

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 14 12:11 EDT 2021. Contains 342949 sequences. (Running on oeis4.)