The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A288213 Fixed point of the mapping 00->0010, 1->011, starting with 00. 5
 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1 COMMENTS From Michel Dekking, Sep 27 2019: (Start) This sequence is a morphic sequence, i.e, the letter-to-letter image of a fixed point of a morphism. Proof: We note first that the mapping SR: 00->0010, 10->011, is an algorithmic procedure given by StringReplace in Mathematica. This makes it hard to describe iterates of it. However, in this particular case one can deal with this. There are three types of 0's occurring in (a(n)). The first 0 in a pair 00, which we code by the letter F, the second 0 in a pair 00 which we code by the letter G, and the single 0 occurring between two 1's, coded by G. The 1 at the end of the iterates SR^n, we code by D ('dead'). The other 1's we code by A ('active'). So, if we denote this code by psi, then for example,     psi(SR(00)) = psi(0010) = FGAD,     psi(SR^2(00)) = psi(00100110) = FGAFGAAD. Now consider the morphism sigma on the alphabet {F,G,D,A} given by     sigma(F) = FGA, sigma(G) = F, sigma(D) = D, sigma(A) = GAA. Let pi be the inverse of psi: pi(F) = pi(G) = pi(D) = 0, pi(A) = 1. Any word with prefix 00 and without occurrences of 000, is a concatenation of the three words u=00, v=1 and w=101. The SR-procedure acts context-free on such concatenations. One has     SR(u) = 0010,  SR(v) = 011, SR(w) = 0110011. The psi-images are     psi(u) = FG, psi(v) = A, psi(w) = AGA. The sigma-images of these are     sigma(FG) = FGAF, sigma(A) = GAA, sigma(AGA) = GAAFGAA. The pi-images of these are     pi sigma psi(u) = 0010, pi sigma psi(v) = 011, pi sigma psi(w) = 0110011. We see that pi sigma psi acts exactly in the same way as SR. It follows that (a(n)) = pi(x), where x = FGAFGAA... is the unique fixed point of sigma. QED (End) From Michel Dekking, Sep 27 2019: (Start) Now that we know that this sequence is a morphic sequence, we may prove Kimberling's conjecture that the lengths of the words SR^n(00) are given by A182780. Here b:=A182780 has b(0) = 2, b(1) = 4, and satisfies the linear recurrence b(n) = 3*b(n-1) - b(n-2) - b(n-3) for n>2. The number of letters (F's, G's, D's and A's) in the word psi(SR^n(00)) is equal to the vector/matrix/vector product     (1,1,1,1) M^n (1,0,1,0)^T, where (1,0,1,0)^T is the transpose of (1,0,1,0), and M is the incidence matrix of the morphism sigma, i.e., M equals     |1 1 0 0|     |1 0 0 1|     |0 0 1 0|     |1 0 0 2|. The characteristic polynomial of M is equal to     chi(u) = u^4 - 4u^3 + 4u^2 - 1 = (u^3 - 3u^2 + u + 1)(u - 1). Thus the conjecture is proved by an application of the Cayley-Hamilton theorem:  M^3 = 3M^2 - M - Id. (End) From Michel Dekking, Sep 28 2019: (Start) The application of Cayley-Hamilton is more subtle than suggested above. In fact chi(u) has a second factor u-1: chi(u) =  (u^2-2u-1)(u-1)^2, but b=A182780 does not satisfy the Pell recurrence a(n) = 2*a(n-1) + a(n-2). Removing the letter D from {F,G,D,A} gives a morphism tau defined by     tau(F) = FGA, tau(G) = F, tau(A) = GAA. The iterates tau^n(F) are equal to the iterates sigma^n(FD), with the suffix D removed. So     |SR^n(00)|= |sigma^n(FD)|=|tau^n(F)|+1, where |.| denotes length. The characteristic polynomial of the incidence matrix of tau is equal to u^3-3u^2+u+1. So, by the Cayley-Hamilton theorem, the sequence     (|tau^n(F)|) = 1,3,7,17,41,99,... = A078057=:c satisfies the recurrence c(n) = 3c(n-1)-c(n-2)-c(n-3). This implies that the sequence (|SR^n(00)|) = (c(n)+1) satisfies the recurrence b(n) = 3b(n-1) - b(n-2) - b(n-3). QED (End) LINKS Clark Kimberling, Table of n, a(n) for n = 1..10000 FORMULA a(n) = A001953(n-1) mod 2 (conjectured). - Jon Maiga, Sep 27 2019 EXAMPLE Iterates, starting with 00: 00 0010 00100110 001001100100110110 001001100100110110010011001001101100110110 MATHEMATICA s = {0, 0}; w = StringJoin[Map[ToString, s]]; w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "011"}] Table[w[n], {n, 0, 8}] st = ToCharacterCode[w] - 48   (* A288213 *) Flatten[Position[st, 0]]  (* A288214 *) Flatten[Position[st, 1]]  (* A288215 *) Table[StringLength[w[n]], {n, 1, 35}] (* A182780 conjectured *) CROSSREFS Cf. A001953, A288214, A288215, A182780. Sequence in context: A131378 A189624 A014707 * A308187 A289007 A308901 Adjacent sequences:  A288210 A288211 A288212 * A288214 A288215 A288216 KEYWORD nonn,easy AUTHOR Clark Kimberling, Jun 07 2017 STATUS approved

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

Last modified May 8 09:57 EDT 2021. Contains 343666 sequences. (Running on oeis4.)