login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A291069 Largest number of distinct words arising in Watanabe's tag system {00, 0111} applied to a binary word w, over all starting words w of length n. 7

%I #23 Sep 23 2021 01:27:14

%S 5,4,4,14,13,12,25,24,23,38,37,36,53,52,51,68,67,66,85,84,83,102,101,

%T 100,119,118,117,138,137,136,157,156,155,176,175,174,195,194,193,214,

%U 213,212,235,234,233,256,255,254,277,276

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

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

%C The empty word is included in the count.

%C Comment from _Don Reble_, Aug 25 2017: (Start)

%C 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 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 The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.

%C Furthermore, the number of important zeros is eventually bounded.

%C 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 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 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 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 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 Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

%p See link.

%Y 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 Cf. A291074.

%K nonn,more

%O 1,1

%A _N. J. A. Sloane_, Aug 18 2017

%E a(8)-(50) from _Lars Blomberg_, Sep 16 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 08:22 EDT 2024. Contains 371236 sequences. (Running on oeis4.)