login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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[0] = StringJoin[Map[ToString, s]];

w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "011"}]

Table[w[n], {n, 0, 8}]

st = ToCharacterCode[w[11]] - 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.

License Agreements, Terms of Use, Privacy Policy. .

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