A292089 - OEIS

%I #37 Aug 10 2018 15:47:09

%S 5,9,11,16,20,22,23,25,37,38,43,47,61,64,66,68,71,82,87,95,100,115,

%T 119,120,123,126,137,141,142,143,144,147,149,153,156,158,164,165,171,

%U 178,179,183,188,195,196,201,202,203,205,206,212,214,216,218,223,232

%N Numbers n such that Watanabe's 3-shift tag system {00/1011} started at the word (100)^n eventually dies (i.e., reaches the empty string).

%C 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.

%C These are the numbers such that A292091(n)=0.

%C Oct 11, 2017: _Lars Blomberg_ has found that 872 is a member of this sequence. The word (100)^872 reaches the empty string after 72392976118788 iterations. The attached graph shows the lengths of the successive words in the trajectory. - _N. J. A. Sloane_, Oct 13 2017

%H Lars Blomberg, <a href="/A292089/b292089.txt">Table of n, a(n) for n = 1..1440</a>

%H Peter R. J. Asveld, <a href="http://doc.utwente.nl/66184/1/1988m20.pdf">On a Post's System of Tag</a>. Bulletin of the EATCS 36 (1988), 96-102.

%H Lars Blomberg, <a href="/A292089/a292089.jpg">Lengths of words in the trajectory of (100)^872</a>

%H N. J. A. Sloane, <a href="/A291792/a291792.txt">Maple code for A291792, A284119, A291793, A284121), A291794, A291795, A291796, A292089, A292090, A292091, A292092, A292093, A292094.</a>

%H Shigeru Watanabe, <a href="/A284116/a284116.pdf">Periodicity of Post's normal process of tag</a>, 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]

%e The following is the analog of columns 3 through 7 of Asveld's Table 1.

%e 1 [171, 6, 56, 59, 138]

%e 2 [166, 6, 56, 59, 133]

%e 3 [11, 6, 16, 17, 10]

%e 4 [154, 6, 56, 59, 121]

%e 5 [105, 0, 0, 31, 24]

%e 6 [14, 518, 28, 85, 215]

%e 7 [57, 6, 38, 41, 36]

%e 8 [68, 518, 42, 85, 333]

%e 9 [173, 0, 0, 49, 38]

%e 10 [1098, 6, 34, 159, 407]

%e 11 [8265, 0, 0, 328, 4429]

%e 12 [720, 6, 34, 93, 343]

%e 13 [1715, 6, 34, 93, 1338]

%e 14 [130, 28, 82, 83, 85]

%e 15 [1979, 6, 20, 215, 720]

%e 16 [2024, 0, 0, 193, 1023]

%e 17 [833, 6, 70, 121, 420]

%e 18 [162, 34, 100, 101, 105]

%e 19 [591, 6, 20, 109, 118]

%e 20 [6124, 0, 0, 357, 2259]

%e 21 [59673, 6, 20, 781, 33530]

%e 22 [748, 0, 0, 150, 328]

%e 23 [11631, 0, 0, 273, 6250]

%e 24 [3200, 6, 56, 261, 1515]

%e ...

%Y Cf. A284116, A291067, A291780, A291781.

%Y Asveld's Table 1 gives data about the behavior of Post's 3-shift tag system {00/1101} applied to the word (100)^n. The first column gives n, the nonzero values in column 2 give A291792, and columns 3 through 7 give A284119, 291793 (or A284121), A291794, A291795, A291796. For the corresponding data for Watanabe's 3-shift tag system {00/1011} applied to (100)^n see A292089, A292090, A292091, A292092, A292093, A292094.

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Sep 10 2017

%E a(8)-(18) from _Lars Blomberg_, Sep 14 2017

%E a(19) and beyond from _Lars Blomberg_, Apr 20 2018