|
%I M0406 #66 Mar 04 2023 01:59:15
%S 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 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 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 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.
%C a(n)=2 if and only if n-1 is in A079523. - _Benoit Cloitre_, Mar 10 2003
%C 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 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 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 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 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 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%D J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 18.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.
%H Roger L. Bagula, <a href="/A007413/a007413.txt">Description of sequence as successive rows of a triangle</a>
%H 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 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 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 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 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 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 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 a(n) = 2 - A029883(n) = 3 - A036577(n). - _Philippe Deléham_, Mar 20 2004
%F 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 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 productions = {"a" -> "abc ", "b" -> "ac ", "c" -> "b ", " " -> ""};
%e NestList[g, "a", 5] // TableForm
%e a
%e abc
%e abc ac b
%e abc ac b abc b ac
%e abc ac b abc b ac abc ac b ac abc b
%e 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 Nest[ Flatten[ # /. {1 -> {1, 2, 3}, 2 -> {1, 3}, 3 -> {2}}] &, {1}, 7] (* _Robert G. Wilson v_, May 07 2005 *)
%o (PARI) {a(n) = if( n<1 || valuation(n, 2)%2, 2, 2 + (-1)^subst( Pol(binary(n)), x,1))};
%o (Python)
%o def A007413(n): return 2-(n.bit_count()&1)+((n-1).bit_count()&1) # _Chai Wah Wu_, Mar 03 2023
%Y Cf. A001285, A010060.
%Y First differences of A000069.
%Y Equals A036580(n-1) + 1.
%Y Cf. A115384, A159481, A079523, A000120.
%K nonn,easy
%O 1,2
%A _N. J. A. Sloane_
|
