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.
Original entry on oeis.org
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
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.
- 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
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).
A289673
Take n-th string over {1,2} in lexicographic order and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}) just once.
Original entry on oeis.org
-1, 12, 1, 1, 212, 212, 11, 11, 11, 11, 2212, 2212, 2212, 2212, 111, 211, 111, 211, 111, 211, 111, 211, 12212, 22212, 12212, 22212, 12212, 22212, 12212, 22212, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 112212
Offset: 1
The initial words are:
1,2,11,12,21,22,111,112,121,122,211,212,221,222,1111,...
Applying the tag system over {1,2} these become:
-1, 12, 1, 1, 212, 212, 11, 11, 11, 11, 2212, 2212, 2212, 2212, 111, ...
If we were working over {0,1} the initial strings would be:
0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,...
and applying the tag system over {0,1} described in A284116 these would become:
-1, 01, 0, 0, 101, 101, 00, 00, 00, 00, 1101, 1101, 1101, 1101, 000, ...
-
See A291072.
-
from itertools import product
A289673_list = [-1 if s == ('1',) else int((''.join(s)+('2212' if s[0] == '2' else '11'))[3:]) for l in range(1,10) for s in product('12',repeat=l)] # Chai Wah Wu, Aug 06 2017
A291073
Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 1110} described in A291068 (but adapted to the alphabet {1,2}) just once.
Original entry on oeis.org
-1, 21, 1, 1, 221, 221, 11, 11, 11, 11, 2221, 2221, 2221, 2221, 111, 211, 111, 211, 111, 211, 111, 211, 12221, 22221, 12221, 22221, 12221, 22221, 12221, 22221, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111
Offset: 1
A291074
Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 0111} described in A291069 (but adapted to the alphabet {1,2}) just once.
Original entry on oeis.org
-1, 22, 1, 1, 222, 222, 11, 11, 11, 11, 1222, 1222, 1222, 1222, 111, 211, 111, 211, 111, 211, 111, 211, 11222, 21222, 11222, 21222, 11222, 21222, 11222, 21222, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111
Offset: 1
A291075
Trajectory of the word "211" under the Watanabe tag system {11, 2122} described in A291067 (adapted to the alphabet {1,2}).
Original entry on oeis.org
211, 2122, 22122, 222122, 1222122, 212211, 2112122, 21222122, 221222122, 2221222122, 12221222122, 2122212211, 22122112122, 221121222122, 1212221222122, 222122212211, 1222122112122, 212211212211, 2112122112122, 21221121222122, 211212221222122, 2122212221222122
Offset: 1
Showing 1-5 of 5 results.
Comments