login
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.
16
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
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]
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).
Sequence in context: A189422 A266980 A130554 * A037054 A284740 A155797
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Aug 18 2017
EXTENSIONS
a(8)-(42) from Lars Blomberg, Sep 16 2017
STATUS
approved