cp's OEIS Frontend

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

%I A291068 #28 Sep 23 2021 01:27:10
%S A291068 6,5,4,15,14,13,26,25,24,39,38,37,54,53,52,69,68,67,86,85,84,103,102,
%T A291068 101,120,119,118,139,138,137,158,157,156,177,176,175,196,195,194,215,
%U A291068 214,213,236,235,234,257,256,255,278,277
%N A291068 Largest number of distinct words arising in Watanabe's tag system {00, 1110} applied to a binary word w, over all starting words w of length n.
%C A291068 Watanabe's tag system {00, 1110} 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 1110 to w and deleting the first three letters.
%C A291068 The empty word is included in the count.
%C A291068 Comment from _Don Reble_, Aug 25 2017: (Start)
%C A291068 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.
%C A291068 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.
%C A291068 The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.
%C A291068 Furthermore, the number of important zeros is eventually bounded.
%C A291068 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.
%C A291068 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
%C A291068 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)
%H A291068 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]
%H A291068 N. J. A. Sloane, <a href="/A291067/a291067.txt">Maple programs that compute first 7 terms for each of A284116, A291067, A291068, A291069</a>
%e A291068 Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".
%p A291068 See link.
%Y A291068 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).
%Y A291068 Cf. A291073.
%K A291068 nonn,more
%O A291068 1,1
%A A291068 _N. J. A. Sloane_, Aug 18 2017
%E A291068 a(8)-(50) from _Lars Blomberg_, Sep 16 2017