This site is supported by donations to The OEIS Foundation.

 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
 5, 4, 4, 14, 13, 12, 25, 24, 23, 38, 37, 36, 53, 52, 51, 68, 67, 66, 85, 84, 83, 102, 101, 100, 119, 118, 117, 138, 137, 136, 157, 156, 155, 176, 175, 174, 195, 194, 193, 214, 213, 212, 235, 234, 233, 256, 255, 254, 277, 276 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS 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. The empty word is included in the count. Comment from Don Reble, Aug 25 2017: (Start) 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 affect on the outcome. 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. The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779. Furthermore, the number of important zeros is eventually bounded. 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. 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 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) 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", "000", "1001", "10010", "100100", "1001001". 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). Cf. A291074. Sequence in context: A244046 A255332 A071419 * A019117 A204372 A279918 Adjacent sequences:  A291066 A291067 A291068 * A291070 A291071 A291072 KEYWORD nonn,more AUTHOR N. J. A. Sloane, Aug 18 2017 EXTENSIONS a(8)-(50) from Lars Blomberg, Sep 16 2017 STATUS approved

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

Last modified October 17 15:01 EDT 2019. Contains 328116 sequences. (Running on oeis4.)