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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A288729 0-limiting word of the mapping 00->1000, 10->01, starting with 00. 8
0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0 (list; graph; refs; listen; history; text; internal format)
OFFSET

1

COMMENTS

Iterates of the mapping, starting with 00:

00

1000

011000

01011000

0011011000

10001011011000

011000011011011000

0101100001011011011000

00110110000011011011011000

1000101101100010001011011011011000

The 0-limiting word is the limit of the n-th iterates for n = 0 mod 4.

Conjecture: the number of letters (0s and 1s) in the n-th iterate is given by A288732(n), for n >= 0.

From Michel Dekking, Mar 29 2018: (Start)

Here is a proof of the conjecture. We note first that the mapping

SR: 00->1000, 10->01, is an algorithmic procedure given by StringReplace in Mathematica (see also comments of A289035). This makes it hard to describe iterates of SR. However, in this particular case the iterates have a remarkable structure. Let

    B0:=0000, B1:=00010001, B2:=000, B3:=00001.

Moreover let S:=011. We call S a separator: the middle 1 in S is not part of the 2-block 00, nor of the 2-block 10, which makes this middle 1 inert for SR. The consequence is that the action of SR is context-free between two separators.

Let W(n) = u SR^n(00) u^{-1} be the conjugate of S by the word u=000, then  of course W(n) and SR^n(00) have the same length.

Examples:

    W(0) = SR^{0}(00) = 00,

    W(1) = 0001, since SR^{1}(00) = 1000,

    W(2) = 000011, since SR^{2}(00) = 011000,

    W(3) = 00001011, since SR^{3}(00) = 01011000,

    W(4) = 0000011011, since SR^{4}(00) = 0011011000.

    W(5) = 00010001011011, since SR^{5}(00) = 10001011011000.

The action of SR on a B-block between separators is approximately (ignoring the borders of the words) given by

    S B(j) S -> S B(j+1) S for j=0,2,3 and

    S B(1) S -> S B(2) S B(2) S.

It follows from this that W(n) is a concatenation of just separators S and words B(j) if n equals j modulo 4, as soon as n>1.

The separators occur as singletons between two B(j)'s, or as a chain SS...S. The singletons and the chains are always preceded by 00 or by 01. More precisely: in W(n) they are all preceded by 00 if n is even, and always by 01 if n is odd. If a chain of length L in W(n) is preceded by 00, then it generates a chain of length L in W(n+1), but if it is preceded by 01, then it generates a chain of length L+1 in W(n+1).

It follows from all this that the best way to describe the iterates of SR is to take cycles of length 4, i.e., to give an expression for W(4k+j).

Here is what happens for j=3: the number of B(j) blocks in W(4k+3) equals 2^k; actually this happens for all j because of the SB(1)S -> S B(2)SB(2)S action. For the same reason the number of singleton S-blocks equals 2^{k-1}. The S-chains will only have an odd length. The start is from a singleton S for k=0. For k=1 there is a singleton S, and a chain of length 3. The number of S-chains of length 2L-1 in W(4k+3) is equal to 2^{k-L} for L=1,2,..,k-1, including the singletons. In addition there is an S-chain of length 2k+1 (generated by the chain of length 3 in W(7)).

The length of W(4k+3) for k>0 will therefore be equal to

    |W(4k+3)| = 5*2^k + 3*[ 1*2^{k-1} + 3*2^{k-2}+ ... +(2k-3)*2 + (2k-1)*1] + 3*(2k+1).

Here the sum in square brackets is the convolution of the powers of two with the odd numbers (for n=k-1, see A050488), which gives

    |W(4k+3)| = 5*2^k + 3*[ 3*2^k - 2(k-1) -5] + 6*k+3 = 14*2^k - 6 = 7*2^{k+1}- 6.

This proves |W(4k+3)| = A288732(4k+3).

Similarly one shows that |W(4k+j)| = A288732(4k+j) for the other j.

(End)

LINKS

Clark Kimberling, Table of n, a(n) for n = 1..10000

EXAMPLE

The first three n-th iterates for n == 0 mod 3 are

00

0011011000

00110110000011011011011000

MATHEMATICA

s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];

w[n_] := StringReplace[w[n - 1], {"00" -> "1000", "10" -> "01"}]

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

st = ToCharacterCode[w[20]] - 48   (* A288729 *)

Flatten[Position[st, 0]]  (* A288730 *)

Flatten[Position[st, 1]]  (* A288731 *)

Table[StringLength[w[n]], {n, 0, 20}] (* A288732 *)

CROSSREFS

Cf. A288729, A288730, A288731, A288732, A288733 (1-limiting word), A288741 (3-limiting word).

Sequence in context: A257000 A062301 A181712 * A286807 A126564 A180433

Adjacent sequences:  A288726 A288727 A288728 * A288730 A288731 A288732

KEYWORD

nonn,easy

AUTHOR

Clark Kimberling, Jun 16 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 February 20 08:44 EST 2019. Contains 320325 sequences. (Running on oeis4.)