|
%I #23 Sep 28 2019 10:01:23
%S 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,
%T 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,
%U 0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,1,0
%N Fixed point of the mapping 00->0010, 1->011, starting with 00.
%C From _Michel Dekking_, Sep 27 2019: (Start)
%C This sequence is a morphic sequence, i.e, the letter-to-letter image of a fixed point of a morphism.
%C 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.
%C 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').
%C So, if we denote this code by psi, then for example,
%C psi(SR(00)) = psi(0010) = FGAD,
%C psi(SR^2(00)) = psi(00100110) = FGAFGAAD.
%C Now consider the morphism sigma on the alphabet {F,G,D,A} given by
%C sigma(F) = FGA, sigma(G) = F, sigma(D) = D, sigma(A) = GAA.
%C Let pi be the inverse of psi: pi(F) = pi(G) = pi(D) = 0, pi(A) = 1.
%C 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
%C SR(u) = 0010, SR(v) = 011, SR(w) = 0110011.
%C The psi-images are
%C psi(u) = FG, psi(v) = A, psi(w) = AGA.
%C The sigma-images of these are
%C sigma(FG) = FGAF, sigma(A) = GAA, sigma(AGA) = GAAFGAA.
%C The pi-images of these are
%C pi sigma psi(u) = 0010, pi sigma psi(v) = 011, pi sigma psi(w) = 0110011.
%C We see that pi sigma psi acts exactly in the same way as SR.
%C It follows that (a(n)) = pi(x), where x = FGAFGAA... is the unique fixed point of sigma. QED
%C (End)
%C From _Michel Dekking_, Sep 27 2019: (Start)
%C 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.
%C 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.
%C 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
%C (1,1,1,1) M^n (1,0,1,0)^T,
%C 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
%C |1 1 0 0|
%C |1 0 0 1|
%C |0 0 1 0|
%C |1 0 0 2|.
%C The characteristic polynomial of M is equal to
%C chi(u) = u^4 - 4u^3 + 4u^2 - 1 = (u^3 - 3u^2 + u + 1)(u - 1).
%C Thus the conjecture is proved by an application of the Cayley-Hamilton theorem: M^3 = 3M^2 - M - Id.
%C (End)
%C From _Michel Dekking_, Sep 28 2019: (Start)
%C 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).
%C Removing the letter D from {F,G,D,A} gives a morphism tau defined by
%C tau(F) = FGA, tau(G) = F, tau(A) = GAA.
%C The iterates tau^n(F) are equal to the iterates sigma^n(FD), with the suffix D removed. So
%C |SR^n(00)|= |sigma^n(FD)|=|tau^n(F)|+1,
%C where |.| denotes length.
%C The characteristic polynomial of the incidence matrix of tau is equal to u^3-3u^2+u+1.
%C So, by the Cayley-Hamilton theorem, the sequence
%C (|tau^n(F)|) = 1,3,7,17,41,99,... = A078057=:c
%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
%C b(n) = 3b(n-1) - b(n-2) - b(n-3). QED
%C (End)
%H Clark Kimberling, <a href="/A288213/b288213.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = A001953(n-1) mod 2 (conjectured). - _Jon Maiga_, Sep 27 2019
%e Iterates, starting with 00:
%e 00
%e 0010
%e 00100110
%e 001001100100110110
%e 001001100100110110010011001001101100110110
%t s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
%t w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "011"}]
%t Table[w[n], {n, 0, 8}]
%t st = ToCharacterCode[w[11]] - 48 (* A288213 *)
%t Flatten[Position[st, 0]] (* A288214 *)
%t Flatten[Position[st, 1]] (* A288215 *)
%t Table[StringLength[w[n]], {n, 1, 35}] (* A182780 conjectured *)
%Y Cf. A001953, A288214, A288215, A182780.
%K nonn,easy
%O 1
%A _Clark Kimberling_, Jun 07 2017
|
