login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.
(Formerly M0406)
20

%I M0406

%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 Zeichenreihe. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7:1a22, 1906.

%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="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.

%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))};

%Y Cf. A001285, A010060.

%Y First differences of A000069.

%Y Equals A036580(n-1) + 1.

%Y Cf. A115384 A159481 A007413 A000120.

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 6 12:54 EST 2016. Contains 278781 sequences.