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

Author

N. J. A. Sloane, Aug 18 2017

Keywords

• nonn

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

Examples

			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.
		

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

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.

Programs

Maple

See link.

Extensions

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