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

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,2

Comments

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

References

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.

Links

Table of n, a(n) for n=1..105.

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.

Formula

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

Example

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

Mathematica

Nest[ Flatten[ # /. {1 -> {1, 2, 3}, 2 -> {1, 3}, 3 -> {2}}] &, {1}, 7] (* Robert G. Wilson v, May 07 2005 *)

Prog

(PARI) {a(n) = if( n<1 || valuation(n, 2)%2, 2, 2 + (-1)^subst( Pol(binary(n)), x, 1))};
(Python)
def A007413(n): return 2-(n.bit_count()&1)+((n-1).bit_count()&1) # Chai Wah Wu, Mar 03 2023

Crossrefs

Cf. A001285, A010060.

First differences of A000069.

Equals A036580(n-1) + 1.

Cf. A115384, A159481, A079523, A000120.

Sequence in context: A369010 A260449 A135511 * A277750 A325520 A072457

Adjacent sequences: A007410 A007411 A007412 * A007414 A007415 A007416

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved