A291069 Largest number of distinct words arising in Watanabe's tag system {00, 0111} applied to a binary word w, over all starting words w of length n.

5, 4, 4, 14, 13, 12, 25, 24, 23, 38, 37, 36, 53, 52, 51, 68, 67, 66, 85, 84, 83, 102, 101, 100, 119, 118, 117, 138, 137, 136, 157, 156, 155, 176, 175, 174, 195, 194, 193, 214, 213, 212, 235, 234, 233, 256, 255, 254, 277, 276

Offset

1,1

Comments

Watanabe's tag system {00, 0111} maps a word w over {0,1} to w', where if w begins with 0, w' is obtained by appending 00 to w and deleting the first three letters, or if w begins with 1, w' is obtained by appending 0111 to w and deleting the first three letters.

The empty word is included in the count.

Comment from Don Reble, Aug 25 2017: (Start)

The following comment applies to both the 3-shift tag systems {00,1110} (A291068) and {00,0111} (A291069). Number the bits in a binary word w starting at the left with bit 0. For the trajectory of w under the tag system, only bits numbered 0,3,6,9,... are important, the others (the unimportant bits) having no effect on the outcome.

An important 1 bit produces 0111 or 1110, and exactly one of those new 1 bits is important. The number of important 1's never changes. So the number of initial words of length n that terminate (the analog of A289670) is just 2^(number-of-unimportant-bits) = 2^(floor(2*n/3)) = A291778.

The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.

Furthermore, the number of important zeros is eventually bounded.

Proof. If a word has A important zeros and B important ones, then after A+B steps, there will be at most 2A+4B bits, and at most (2A+4B+2)/3 important bits. B of them are important ones, so at most (2A+B+2)/3 are important zeros.

If A >= B+3, then (2A+B+2)/3 <= (2A+A-1)/3 < A. If A < B+3, then (2A+B+2)/3 < (3B+8)/3 = B+2. The first kind must shrink; the second kind can't grow past A+B+2. QED

Ultimately, a word with B important ones has at most A+B+2 important bits, so can't diverge. So the word "finite" in the definition was unnecessary and has been omitted. (End)

Links

Table of n, a(n) for n=1..50.

Shigeru Watanabe, Periodicity of Post's normal process of tag, in Jerome Fox, ed., Proceedings of Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press, Polytechnic Institute of Brooklyn, 1963, pp. 83-99. [Annotated scanned copy]

N. J. A. Sloane, Maple programs that compute first 7 terms for each of A284116, A291067, A291068, A291069

Example

Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

Maple

See link.

Crossrefs

For the 3-shift tag systems {00,1101}, {00, 1011}, {00, 1110}, {00, 0111} see A284116, A291067, A291068, A291069 respectively (as well as the cross-referenced entries mentioned there).

Cf. A291074.

Sequence in context: A244046 A255332 A071419 * A019117 A204372 A279918

Adjacent sequences: A291066 A291067 A291068 * A291070 A291071 A291072

Keyword

nonn,more

Author

N. J. A. Sloane, Aug 18 2017

Extensions

a(8)-(50) from Lars Blomberg, Sep 16 2017

Status

approved