A036580 -id:A036580 - cp's OEIS frontend

A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.

1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 2, 3

Offset: 1

N. J. A. Sloane

a(n)=2 if and only if n-1 is in A079523. - Benoit Cloitre, Mar 10 2003
Partial sums modulo 4 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... - Philippe Deléham, Mar 04 2004
To construct the sequence: start with 1 and concatenate 4 -1 = 3: 1, 3, then change the last term (2 -> 1, 3 ->2 ) gives 1, 2. Concatenate 1, 2 with 4 -1 = 3, 4 - 2 = 2: 1, 2, 3, 2 and change the last term: 1, 2, 3, 1. Concatenate 1, 2, 3, 1 with 4 - 1 = 3, 4 - 2 = 2, 4 - 3 = 1, 4 - 1 = 3: 1, 2, 3, 1, 3, 2, 1, 3 and change the last term: 1, 2, 3, 1, 3, 2, 1, 2 etc. - Philippe Deléham, Mar 04 2004
To construct the sequence: start with the Thue-Morse sequence A010060 = 0, 1, 1, 0, 1, 0, 0, 1, ... Then change 0 -> 1, 2, 3,  and 1 -> 3, 2, 1,  gives: 1, 2, 3, , 3, 2, 1, ,3, 2, 1, , 1, 2, 3, , 3, 2, 1, , ... and fill in the successive holes with the successive terms of the sequence itself. - _Philippe Deléham, Mar 04 2004
To construct the sequence: to insert the number 2 between the A003156(k)-th term and the (1 + A003156(k))-th term of the sequence 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, ... - Philippe Deléham, Mar 04 2004
Conjecture. The sequence is formed by the numbers of 1's between every pair of consecutive 2's in A076826. - Vladimir Shevelev, May 31 2009

			Here are the first 5 stages in the construction of this sequence, together with Mma code, taken from Keranen's article. His alphabet is a,b,c rather than 1,2,3.
productions = {"a" -> "abc ", "b" -> "ac ", "c" -> "b ", " " -> ""};
NestList[g, "a", 5] // TableForm
a
abc
abc ac b
abc ac b abc b ac
abc ac b abc b ac abc ac b ac abc b
abc ac b abc b ac abc ac b ac abc b abc ac b abc b ac abc b abc ac b ac

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.

Paolo Xausa, Table of n, a(n) for n = 1..10000
Roger L. Bagula, Description of sequence as successive rows of a triangle
James D. Currie, Non-repetitive words: Ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 20.
James D. Currie, Palindrome positions in ternary square-free words, Theoretical Computer Science, 396 (2008) 254-257.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
V. Keranen, New Abelian Square-Free DT0L-Languages over 4 Letters, Theoretical Computer Science, Volume 410, Issues 38-40, 6 September 2009, Pages 3893-3900.
S. Kitaev and T. Mansour, Counting the occurrences of generalized patterns in words generated by a morphism, arXiv:math/0210170 [math.CO], 2002.
Andrzej Tomski and Maciej Zakarczemny, A note on Browkin's and Cao's cancellation algorithm, Technical Transections 7/2018.

Cf. A001285, A010060.
First differences of A000069.
Equals A036580(n-1) + 1.
Cf. A115384, A159481, A079523, A000120.

Nest[ Flatten[ # /. {1 -> {1, 2, 3}, 2 -> {1, 3}, 3 -> {2}}] &, {1}, 7] (* Robert G. Wilson v, May 07 2005 *)
2 - Differences[ThueMorse[Range[0, 100]]] (* Paolo Xausa, Oct 25 2024 *)

{a(n) = if( n<1 || valuation(n, 2)%2, 2, 2 + (-1)^subst( Pol(binary(n)), x,1))};

def A007413(n): return 2-(n.bit_count()&1)+((n-1).bit_count()&1) # Chai Wah Wu, Mar 03 2023

a(n) modulo 2 = A035263(n). a(A036554(n)) = 2. a(A003159(n)) = 1 if n odd. a(A003159(n)) = 3 if n even. a(n) = A033485(n) mod 4. a(n) = 4 - A036585(n-1). - Philippe Deléham, Mar 04 2004
a(n) = 2 - A029883(n) = 3 - A036577(n). - Philippe Deléham, Mar 20 2004
For n>=1, we have: 1) a(A108269(n))=A010684(n-1); 2) a(A079523(n))=A010684(n-1); 3) a(A081706(2n))=A010684(n). - Vladimir Shevelev, Jun 22 2009

A356133 Complement of A026430.

Original entry on oeis.org

2, 4, 7, 11, 13, 17, 20, 22, 25, 29, 32, 34, 38, 40, 43, 47, 49, 53, 56, 58, 62, 64, 67, 71, 74, 76, 79, 83, 85, 89, 92, 94, 97, 101, 104, 106, 110, 112, 115, 119, 122, 124, 127, 131, 133, 137, 140, 142, 146, 148, 151, 155, 157, 161, 164, 166, 169, 173, 176

Offset: 1

Clark Kimberling, Aug 04 2022

			The partial sums of the Thue-Morse sequence A001285 = (1,2,2,1,2,1,1,...) are A026430 = (0,1,3,5,6,8,9,10,...), from which the missing positive integers are (2,4,7,11,...).

Winston de Greef, Table of n, a(n) for n = 1..5000

Cf. A001285, A007413, A026430, A036580, A091855, A036554, A091855, A354384.

u = Accumulate[1 + ThueMorse /@ Range[0, 2^7]]; (* A026430 *)
Complement[Range[Max[u]], u]  (* A356133 *)

a(n) = 3*n - 1 - hammingweight(n-1)%2; \\ Kevin Ryde, Aug 04 2022

def A356133(n): return 3*n-(2 if (n-1).bit_count()&1 else 1) # Chai Wah Wu, Mar 01 2023

a(n) = 3n - A001285(n-1) for n >= 1.

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

Original entry on oeis.org

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

N. J. A. Sloane

nonn

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)

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

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

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.

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

See A007413, A036580 for other versions.

(* 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 *)

{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 */

def A036577(n): return (n.bit_count()&1)+((n-1).bit_count()&1^1) # Chai Wah Wu, Mar 03 2023

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
a(n) = A010060(2*n - 1) + A010060(2*n) = A115384(2*n) - A115384(2*n - 2). - Zhuorui He, Jul 11 2025

A085794 Lexicographically earliest squarefree infinite ternary word.

Original entry on oeis.org

0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1

Offset: 0

Claude Lenormand (claude.lenormand(AT)free.fr), Jul 24 2003; corrected Jul 25 2003

nonn

Open Problem 1.10.2 in the Allouche & Shallit reference asks for a good alternate characterization of this sequence. (Is it morphic, if so for which morphism?)
The sequence cannot be constructed in a greedy way (without backtracking) choosing each a(n) simply such that the sequence is squarefree: After (0, 1, 0, 2, 0, 1) the greedy choice would be to append 0, but then one is stuck for the alphabet {0,1,2}. If the alphabet is infinite, this greedy procedure yields A007814. - M. F. Hasler, Nov 28 2019
We know that an infinite ternary squarefree word exists, namely the ternary Thue-Morse sequence A036580 = A007413(.+1) - 1. The space of squarefree words is closed (limit of a sequence of squarefree words is again squarefree, using e.g. topology induced by d(x,y) = Sum_{k>=0} |x_k - y_k|/3^k or exp(-min{k: x_k != y_k})) and compact, so the inf exists and is reached for some element. [Thanks to Jean-Paul Allouche.] - M. F. Hasler, Nov 29 2019
From Thomas Anton, May 01 2022: (Start)
A direct proof of this is as follows: as noted above we may obtain the sequence through a greedy algorithm with backtracking. This process eliminates as a prefix for any squarefree word, any word lexicographically earlier than an initial segment of this word. Since distinct words must have distinct prefixes of some length, any other squarefree word must be lexicographically later.
Additionally, it is not necessary to show that the inf exists since lexicographically ordered infinite words on a finite alphabet form a complete total ordering. (End)

			From _M. F. Hasler_, Nov 29 2019: (Start)
After a(0) = 0 one must have a(1) = 1 because 00 is not squarefree, i.e., it has a subsequence X = 0 such that XX = 00 is also a subsequence.
After (0,1) one has again a(2) = 0, but then a(3) must be different from 0 (to avoid 00) and from 1 to avoid XX with X = 01, so a(3) = 2.
Then again a(4) = 0 and a(5) = 1.
Now it looks that a(6) could be equal to 0, but with this choice, there would be no possible choice for a(7): all in {0, 1, 2} would produce a square subsequence, in the last case with X = 0102. Since 1 is also excluded, a(6) = 2 is the only possible choice.
A partial subsequence a(0..k) is correct if one can append the infinite ternary Thue-Morse word A036580 and the result is squarefree. (Sufficient but obviously not necessary condition, consider a(k) = A036580(0).) To ensure this, one needs only to check up to twice the length of the prefixed subsequence. (End)

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003, page 30.

Eric Rowland, Table of n, a(n) for n = 0..16383 [These terms are conjectural.]

Cf. A036580, A007413.

A085794_upto(n,A)={ for(n=1+#A+!A,#A=Vec(A,n+2), while( A[n]==A[n-1], while( A[n]++>2, A[n]=0; n--)); for(L=2,(n-1)\2, A[n-L..n-1]!=A[n-2*L..n-L-1] || while(A[n]++>2, A[n]=0; n--) || !n-- || next(2))); A[^-1]} \\ Returns a(0..n). Optional arg allows to specify starting value(s). - M. F. Hasler, Nov 29 2019

More terms from John W. Layman, May 18 2004

Changed b-file to an a-file. - N. J. A. Sloane, Mar 26 2019

A354384 Difference sequence of A356133.

Original entry on oeis.org

2, 3, 4, 2, 4, 3, 2, 3, 4, 3, 2, 4, 2, 3, 4, 2, 4, 3, 2, 4, 2, 3, 4, 3, 2, 3, 4, 2, 4, 3, 2, 3, 4, 3, 2, 4, 2, 3, 4, 3, 2, 3, 4, 2, 4, 3, 2, 4, 2, 3, 4, 2, 4, 3, 2, 3, 4, 3, 2, 4, 2, 3, 4, 2, 4, 3, 2, 4, 2, 3, 4, 3, 2, 3, 4, 2, 4, 3, 2, 4, 2, 3, 4, 2, 4, 3

Offset: 1

Clark Kimberling, Aug 04 2022

Cf. A026430, A356133, A091855 (positions of 2), A036554 (positions of 3), A091855 (positions of 4).

u = Accumulate[1 + ThueMorse /@ Range[0, 200]]  (* A026430 *)
v = Complement[Range[Max[u]], u];  (* A356133 *)
Differences[v] (* A354384 *)

a(n) = A007413(n) + 1.

a(n) = A036580(n) + 2.

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

Original entry on oeis.org

1, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2

Offset: 0

N. J. A. Sloane

nonn

Trajectory of 1 under the morphism 0 -> 12, 1 -> 102 & 2 -> 0. - Robert G. Wilson v, Apr 06 2008

Brian Hayes, Group Theory in the Bedroom and other Mathematical Diversions, Hill and Wang, A division of Farrar, Straus and Giroux, NY, 2008, pages 190-194.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.

Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (1) (2012) 42-46.
Index entries for sequences that are fixed points of mappings

Cf. A005679, A036577, A036579, A036580, A036581, A036582, A036583, A036584, A036585, A036586.

Nest[ # /. {0 -> {1, 2}, 1 -> {1, 0, 2}, 2 -> {0}} &, {0}, 7] // Flatten (* Robert G. Wilson v, Apr 06 2008 *)

A317189 A morphic sequence related to the ternary Thue-Morse sequence.

Original entry on oeis.org

1, 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: 0

N. J. A. Sloane, Jul 30 2018

nonn

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. See proof of Lemma 1.

Cf. A007413, A036577, A036580, A316826.

Nest[Flatten[# /. {1 -> {2, 0}, 2 -> {1}, 0 -> {2, 1, 0}}] &, {2}, 9 (* must be an odd integer*)] (* Robert G. Wilson v, Jul 30 2018 *)

a(n) = A036577(n), n>0, a(0) = 1. - Michel Dekking, Oct 15 2019

More terms from Robert G. Wilson v, Jul 30 2018

cp's OEIS Frontend

A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A356133 Complement of A026430.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A085794 Lexicographically earliest squarefree infinite ternary word.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A354384 Difference sequence of A356133.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A317189 A morphic sequence related to the ternary Thue-Morse sequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula