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

6, 5, 177, 178, 175, 174, 177, 178, 179, 180, 171, 550, 551, 548, 545, 550, 549, 610, 611, 608, 603, 14864, 14863, 14870, 14875, 14876, 15583, 15594, 15741, 15744, 15745, 15742, 15745, 15746, 15743, 114886, 114887, 114884, 114887, 114888, 114885, 404986

Offset

1,1

Comments

Watanabe's tag system {00, 1011} 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 1011 to w and deleting the first three letters.

The empty word is included in the count.

Up through length 60, all starting strings either reach the empty word or enter a loop. - Don Reble, Sep 01 2017

Links

Lars Blomberg, 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", "100", "0001", "10010", "100000", "1000000".
For example, at length 3, the trajectory of 100 begins 100, 1011, 11011, 111011, 0111011, 101100, 1001011, 10111011, 110111011, 1110111011, 01110111011, 1011101100, 11011001011, ..., and goes for 177 steps before a terms is repeated (at the 178-th step). So a(3) = 177. See A291075 for the full trajectory.

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. A291072, A291075, A291780, A291781.

Sequence in context: A189422 A266980 A130554 * A037054 A284740 A155797

Adjacent sequences: A291064 A291065 A291066 * A291068 A291069 A291070

Keyword

nonn

Author

N. J. A. Sloane, Aug 18 2017

Extensions

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

Status

approved