cp's OEIS Frontend

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

%I A007413 M0406 #70 Oct 25 2024 07:23:38
%S A007413 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,
%T A007413 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,
%U A007413 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
%N A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.
%C A007413 a(n)=2 if and only if n-1 is in A079523. - _Benoit Cloitre_, Mar 10 2003
%C A007413 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
%C A007413 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
%C A007413 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
%C A007413 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
%C A007413 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
%D A007413 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%D A007413 J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 18.
%D A007413 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A007413 A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.
%H A007413 Paolo Xausa, <a href="/A007413/b007413.txt">Table of n, a(n) for n = 1..10000</a>
%H A007413 Roger L. Bagula, <a href="/A007413/a007413.txt">Description of sequence as successive rows of a triangle</a>
%H A007413 James D. Currie, <a href="https://doi.org/10.1007/BF01300125">Non-repetitive words: Ages and essences</a>, Combinatorica 16.1 (1996): 19-40. See p. 20.
%H A007413 James D. Currie, <a href="http://dx.doi.org/10.1016/j.tcs.2007.09.015">Palindrome positions in ternary square-free words</a>, Theoretical Computer Science, 396 (2008) 254-257.
%H A007413 F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H A007413 V. Keranen, <a href="http://dx.doi.org/10.1016/j.tcs.2009.05.027">New Abelian Square-Free DT0L-Languages over 4 Letters</a>, Theoretical Computer Science, Volume 410, Issues 38-40, 6 September 2009, Pages 3893-3900.
%H A007413 S. Kitaev and T. Mansour, <a href="http://arxiv.org/abs/math/0210170">Counting the occurrences of generalized patterns in words generated by a morphism</a>, arXiv:math/0210170 [math.CO], 2002.
%H A007413 Andrzej Tomski and Maciej Zakarczemny, <a href="https://doi.org/10.4467/2353737XCT.18.106.8801">A note on Browkin's and Cao's cancellation algorithm</a>, Technical Transections 7/2018.
%F A007413 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
%F A007413 a(n) = 2 - A029883(n) = 3 - A036577(n). - _Philippe Deléham_, Mar 20 2004
%F A007413 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
%e A007413 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.
%e A007413 productions = {"a" -> "abc ", "b" -> "ac ", "c" -> "b ", " " -> ""};
%e A007413 NestList[g, "a", 5] // TableForm
%e A007413 a
%e A007413 abc
%e A007413 abc ac b
%e A007413 abc ac b abc b ac
%e A007413 abc ac b abc b ac abc ac b ac abc b
%e A007413 abc ac b abc b ac abc ac b ac abc b abc ac b abc b ac abc b abc ac b ac
%t A007413 Nest[ Flatten[ # /. {1 -> {1, 2, 3}, 2 -> {1, 3}, 3 -> {2}}] &, {1}, 7] (* _Robert G. Wilson v_, May 07 2005 *)
%t A007413 2 - Differences[ThueMorse[Range[0, 100]]] (* _Paolo Xausa_, Oct 25 2024 *)
%o A007413 (PARI) {a(n) = if( n<1 || valuation(n, 2)%2, 2, 2 + (-1)^subst( Pol(binary(n)), x,1))};
%o A007413 (Python)
%o A007413 def A007413(n): return 2-(n.bit_count()&1)+((n-1).bit_count()&1) # _Chai Wah Wu_, Mar 03 2023
%Y A007413 Cf. A001285, A010060.
%Y A007413 First differences of A000069.
%Y A007413 Equals A036580(n-1) + 1.
%Y A007413 Cf. A115384, A159481, A079523, A000120.
%K A007413 nonn,easy
%O A007413 1,2
%A A007413 _N. J. A. Sloane_