A291792 -id:A291792 - cp's OEIS frontend

A284116 a(n) = largest number of distinct words arising in Post's tag system {00, 1101} applied to a binary word w, over all starting words w of length n, or a(n) = -1 if there is a word w with an unbounded trajectory.

4, 7, 6, 7, 22, 23, 24, 25, 30, 31, 34, 421, 422, 423, 422, 423, 424, 2169, 2170, 2171, 2170, 2171, 2172, 2165, 2166, 2167, 24566, 24567, 24568, 24567, 24568, 24569, 24568, 24569, 24570, 253513, 253514, 342079, 342080, 342083, 342084, 342103, 20858070

Offset: 1

Jeffrey Shallit, Mar 20 2017

nonn

Post's tag system {00, 1101} 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 1101 to w and deleting the first three letters.
The empty word is included in the count.
It is an important open question to decide if there is any word whose orbit grows without limit. - N. J. A. Sloane, Jul 30 2017, based on an email from Allan C. Wechsler
Comment from Don Reble, Aug 01 2017: For n <= 57, all words reach the empty word or a cycle. - N. J. A. Sloane, Aug 01 2017
From David A. Corneth, Aug 02 2017: (Start)
A word w can be described by the pair (c, d) where c is the length of w and d is the number represented by the binary word w. Then 0 <= d < 2^c.
Appending a word ww of m letters to w is the same as setting d to 2^m * w + ww. Preserving only the rightmost q digits of w is the same as setting w to w mod 2^q.
Lastly, we're only really interested in the 1st, 4th, 7th, ... leftmost digits. The others could without loss of generality be set to 0. This can be done with bitand(x, y), with y in A033138.
Therefore this problem can be formulated as follows: Let w = (c, d).
Then if d < 2^(c - 1), w' = (c - 1, bitand(4*d, floor(2^(c + 1) / 7)))
else (if (d >= 2^(c - 1)), w' = (c + 1, bitand(16*d + 13, floor(2^(c + 3) / 7))).
To find a(n), it would be enough to check values d in A152111 with n binary digits and c = n.
(End)
a(110) >= 43913328040672, from w = (100)^k, k=110. - N. J. A. Sloane, Oct 23 2017, based on Lars Blomberg's work on A291792.

			Suppose n=1. Then w = 0 ->000 -> w' = empty word, and w = 1 -> 11101 -> w' = 01 -> 0100 -> w'' = 0 -> 000 -> w''' = empty word. So a(1) = 4 by choosing w = 1.
For n = 5 the orbit of the word 10010 begins 10010, 101101, 1011101, ..., 0000110111011101, and the next word in the orbit has already appeared. The orbit consists of 22 distinct words.
From _David A. Corneth_, Aug 02 2017: (Start)
The 5-letter word w = 10100 can be described as (a, b) = (5, 20). This is equivalent to (5, bitand(20, floor(2^7 / 7))) = (5, bitand(20, 18)) = (5, 16).
As 16 >= 2^(5-1), w' = (5 + 1, bitand(16*16 + 13, floor(2^(5 + 3) / 7))) = (6, bitand(279, 36)) = (6, 4). w'' = w = (5, 16) so 10100 ~ 10000 ends in a period. (End)
Words w that achieve a(1) through a(7) are 1, 10, 100, 0001, 10010, 100000, 0001000. - _N. J. A. Sloane_, Aug 17 2017

John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.

Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent, 2007.
Liesbeth De Mol, Tag systems and Collatz-like functions Theoret. Comput. Sci. 390 (2008), no. 1, 92-101.
Liesbeth De Mol, On the complex behavior of simple tag systems—an experimental approach, Theoret. Comput. Sci. 412 (2011), no. 1-2, 97-112.
Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, Amer. J. Math. 65, 197-215, 1943. See page 204.
Don Reble, Python program for A289670.
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]

Cf. A033138, A152111, A284119, A284121, A289670, A289671, A289672, A289673, A289674, A289675, A289676, A289677.
Cf. also A290436-A290441, A290741, A290742, A291792, A291793, A291794, A291795, A291796.
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).

Table[nmax = 0;
 For[i = 0, i < 2^n, i++, lst = {};
  w = IntegerString[i, 2, n];
  While[! MemberQ[lst, w],
   AppendTo[lst, w];
   If[w == "", Break[]];
   If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
    w = StringDrop[w <> "1101", 3]]];
nmax = Max[nmax, Length[lst]]]; nmax, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)
(* Or, using the (c,d) procedure: *)
 Table[nmax = 0;
 For[i = 0, i < 2^n, i++,
  c = n; d = i; lst = {};
  While[! MemberQ[lst, {c, d}],
   AppendTo[lst, {c, d}];
   If[c == 0,  Break[]];
   If[ d < 2^(c - 1),
    d = BitAnd[4*d, 2^(c - 1) - 1]; c--,
    d = BitAnd[16*d + 13, 2^(c + 1) - 1]; c++]];
nmax = Max[nmax, Length[lst]]]; nmax, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)

a(19)-a(43) from Lars Blomberg, Apr 09 2017

Edited by N. J. A. Sloane, Jul 29 2017 and Oct 23 2017 (adding escape clause in case an infinite trajectory exists)

A284119 Preperiod (or threshold) of orbit of Post's {00, 1101} tag system applied to the word (100)^n, or -1 if this word has an unbounded trajectory.

Original entry on oeis.org

4, 15, 10, 25, 411, 47, 2128, 853, 372, 2805, 366, 2603, 703, 37912, 612, 127, 998, 2401, 1200, 623, 5280, 1778, 1462, 4346269, 4129, 3241, 7018, 3885, 14632, 7019, 4564, 4277, 147688, 1857, 11120, 81141, 20204, 3847, 116014, 7635, 6488, 5665, 6142, 73515, 5826, 6062, 3781, 7865, 28630

Offset: 1

Jeffrey Shallit, Mar 20 2017

nonn

Post's tag system 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 1101 to w and deleting the first three letters.
The empty word is included in the count.
The orbit of the word (100)^n for n=110 dies after 43913328040672 iterations. The longest word in the orbit is 31299218, which appeared at iteration 14392308412264. See also A291792. - Lars Blomberg, Oct 04 2017

			For n = 2 the orbit of (100)^2 = 100100 consists of a preperiod of length 15, followed by a periodic portion of length 6:
Preperiod:
100100,
1001101,
11011101,
111011101,
0111011101,
101110100,
1101001101,
10011011101,
110111011101,
1110111011101,
01110111011101,
1011101110100,
11011101001101,
111010011011101,
0100110111011101,
followed by the period:
(011011101110100,
01110111010000,
1011101000000,
11010000001101,
100000011011101,
0000110111011101)
(repeat)

Lars Blomberg, Table of n, a(n) for n = 1..6075
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
Lars Blomberg, Graph of the terms
Lars Blomberg, Graph of preperiod of a(110)
Lars Blomberg, Graph of preperiod of a(4974)
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A284116, A284121, A292090.

From Lars Blomberg, Apr 20 2018: (Start)
Using Excel, trendlines were created for the preperiod of the Post Tag and Watanabe Tag systems as follows:
A284119: y = 8.6528*x^2.0831, R^2 = 0.478.
A292090: y = 8.5595*x^2.1033, R^2 = 0.472.
Although the error value is rather large, the curves are quite similar. (End)

Edited by N. J. A. Sloane, Jul 29 2017. Added "escape clause" to the definition, Apr 19 2018.

A284121 Period of orbit of Post's tag system applied to the word (100)^n (version 1), or -1 if the orbit increases without limit.

Original entry on oeis.org

2, 6, 6, 6, 1, 10, 28, 6, 10, 6, 6, 6, 1, 1, 6, 28, 10, 6, 10, 6, 6, 1, 6, 6, 1, 6, 6, 6, 6, 6, 6, 52, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 28, 6, 1, 1, 28, 6, 6, 6, 6, 6, 1, 6, 6, 6, 10, 6, 6, 6, 6, 1, 6, 1, 6, 6, 6, 6, 1, 6, 6, 6, 1, 6, 6, 6, 1, 10, 1, 10, 6, 6

Offset: 1

Jeffrey Shallit, Mar 20 2017

nonn

Post's tag system 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 1101 to w and deleting the first three letters.
The empty word is included in the count.
Here a(n)=1 if the orbit ends at the empty word. On the other hand, Asveld defines a(n) to be zero if that happens, which gives a different sequence, A291793. - N. J. A. Sloane, Sep 04 2017

			For n = 2 the orbit of (100)^2 = 100100 consists of a preperiod of length 15, followed by a periodic portion of length 6. So a(2) = 6.

Lars Blomberg, Table of n, a(n) for n = 1..6075
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.

Cf. A284116, A284119, A291792, A291793.

Edited by N. J. A. Sloane, Jul 29 2017

a(50)-a(83) from Lars Blomberg, Sep 08 2017

A291793 Period of orbit of Post's tag system applied to the word (100)^n (version 2), or -1 if the orbit increases without limit.

Original entry on oeis.org

2, 6, 6, 6, 0, 10, 28, 6, 10, 6, 6, 6, 0, 0, 6, 28, 10, 6, 10, 6, 6, 0, 6, 6, 0, 6, 6, 6, 6, 6, 6, 52, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 28, 6, 0, 0, 28, 6, 6, 6, 6, 6, 0, 6, 6, 6, 10, 6, 6, 6, 6, 0, 6, 0, 6, 6, 6, 6, 0, 6, 6, 6, 0, 6, 6, 6, 0, 10, 0, 10, 6, 6

Offset: 1

N. J. A. Sloane, Sep 04 2017, based on Jeffrey Shallit's A284121

nonn

Post's tag system 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 1101 to w and deleting the first three letters.
The empty word is included in the count.
Here, following Asveld, a(n)=0 if the orbit ends at the empty word. On the other hand, Shallit defines a(n) to be 1 if that happens, which gives a different sequence, A284121.
From A.H.M. Smeets, Jul 16 2020: (Start)
In general a tag as defined by Emil Leon Post, is given by a 4-tuple (Sigma,AF,n,w0), where Sigma is some (nonempty) alphabet, AF is the associated function (sometimes also called set of production rules) AF: Sigma -> Sigma*, n is the deletion number and w0 the initial string.
Here, the period lengths a(n) refer to the tags ({0,1},{(0,00),(1,1101)},3,100^n).
a(n) is an even number. Proof: for each cycle the number of associations (productions) 0 -> 00 must equal the number of associations (productions) 1 -> 1101 applied within a cycle. (End)

			For n = 2 the orbit of (100)^2 = 100100 consists of a preperiod of length 15, followed by a periodic portion of length 6.

Lars Blomberg, Table of n, a(n) for n = 1..6075 (corrected for n=165 by _A.H.M. Smeets_)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
Lars Blomberg, Histogram over non-zero terms
Emil L. Post, Formal reductions of the general combinatorial decision problem., American Journal of Mathematics, Vol. 65, No. 2 (Apr., 1943), pp. 197-215.
Eric Weisstein's World of Mathematics, Tag System

Cf. A284116, A284119, A291792, A284121, A336287, A336327.

def step(w):
    i = 0
    while w[0] != alfabet[i]:
        i = i+1
    w = w+suffix[i]
    return w[n:len(w)]
alfabet, suffix, n, ws, w0, m = "01", ["00","1101"], 3, "100", "", 0
while m < 83:
    w0, m = w0+ws, m+1
    w, ww, i, a = w0, w0, 0, 0
    while w != "" and a == 0:
        w, i = step(w), i+1
        if i%1000 == 0:
            ww = w
        else:
            if w == ww or w == "":
                if w != "":
                    a = i%1000
                print(m,a) # A.H.M. Smeets, Jul 16 2020

a(50)-a(83) from Lars Blomberg, Sep 08 2017

A292091 Period of orbit of Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n.

Original entry on oeis.org

6, 6, 6, 6, 0, 518, 6, 518, 0, 6, 0, 6, 6, 28, 6, 0, 6, 34, 6, 0, 6, 0, 0, 6, 0, 518, 22, 22, 22, 6, 6, 6, 40, 518, 6, 6, 0, 0, 6, 6, 518, 518, 0, 518, 518, 6, 0, 6, 6, 26, 26, 6, 6, 6, 6, 6, 22, 6, 518, 6, 0, 16, 26, 0, 6, 0, 6, 0, 6, 6, 0, 6, 6, 6, 6, 6, 6

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

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.
The empty word is included in the count.
Following Asveld we set a(n)=0 if the orbit ends at the empty word.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
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]

Cf. A284116, A291067, A291780, A291781.

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.

a(25)-(77) from Lars Blomberg, Sep 14 2017

A292090 Preperiod (or threshold) of orbit of Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n.

Original entry on oeis.org

171, 166, 11, 154, 105, 14, 57, 68, 173, 1098, 8265, 720, 1715, 130, 1979, 2024, 833, 162, 591, 6124, 59673, 748, 11631, 3200, 1453, 13740, 2947, 2202, 15101, 1268, 608049, 30758, 29903, 1076, 17547, 2888, 72231, 10154, 2321, 68916, 10965, 2276, 151785, 4678

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

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.

The empty word is included in the count.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
Lars Blomberg, Graph of the terms
Lars Blomberg, Graph of preperiod of a(2263)
Lars Blomberg, Graph of preperiod of a(2540)
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]

Cf. A284116, A284119, A291067, A291780, A291781.

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.

From Lars Blomberg, Apr 20 2018: (Start)
Using Excel, trendlines were created for the preperiod of the Post Tag and Watanabe Tag systems as follows:
A284119: y = 8.6528*x^2.0831, R^2 = 0.478.
A292090: y = 8.5595*x^2.1033, R^2 = 0.472.
Although the error value is rather large, the curves are quite similar. (End)

a(25)-(44) from Lars Blomberg, Sep 14 2017

A292089 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).

Original entry on oeis.org

5, 9, 11, 16, 20, 22, 23, 25, 37, 38, 43, 47, 61, 64, 66, 68, 71, 82, 87, 95, 100, 115, 119, 120, 123, 126, 137, 141, 142, 143, 144, 147, 149, 153, 156, 158, 164, 165, 171, 178, 179, 183, 188, 195, 196, 201, 202, 203, 205, 206, 212, 214, 216, 218, 223, 232

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

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.
These are the numbers such that A292091(n)=0.
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

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..1440
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
Lars Blomberg, Lengths of words in the trajectory of (100)^872
N. J. A. Sloane, Maple code for A291792, A284119, A291793, A284121, A291794, A291795, A291796, A292089, A292090, A292091, A292092, A292093, A292094.
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]

Cf. A284116, A291067, A291780, A291781.

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, A291793 (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.

a(8)-(18) from Lars Blomberg, Sep 14 2017

a(19) and beyond from Lars Blomberg, Apr 20 2018

A292092 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of first word we see that is in the cycle, if the orbit cycles, or 0 if the orbit reaches the empty string, or -1 if the orbit is unbounded.

Original entry on oeis.org

56, 56, 16, 56, 0, 28, 38, 42, 0, 34, 0, 34, 34, 82, 20, 0, 70, 100, 20, 0, 20, 0, 0, 56, 0, 46, 64, 64, 64, 92, 74, 34, 118, 66, 88, 52, 0, 0, 34, 268, 42, 34, 0, 46, 30, 92, 0, 16, 34, 76, 76, 34, 34, 38, 110, 20, 64, 92, 46, 56, 0, 46, 76, 0, 74, 0, 88, 0

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

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.
The empty word is included in the count.
Following Asveld we set a(n)=0 if the orbit ends at the empty word.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
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]

Cf. A284116, A291067, A291780, A291781.

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.

a(25)-(68) from Lars Blomberg, Sep 14 2017

A292093 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of the longest word in the orbit, or -1 if the orbit is unbounded.

Original entry on oeis.org

59, 59, 17, 59, 31, 85, 41, 85, 49, 159, 328, 93, 93, 83, 215, 193, 121, 101, 109, 357, 781, 150, 273, 261, 171, 341, 182, 229, 551, 187, 2627, 593, 503, 187, 400, 261, 1369, 371, 226, 1045, 374, 280, 849, 375, 437, 255, 667, 365, 291, 2972, 463, 905, 631, 405

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

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.

The empty word is included in the count.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
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]

Cf. A284116, A291067, A291780, A291781.

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.

a(25)-(54) from Lars Blomberg, Sep 14 2017

A292094 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

Original entry on oeis.org

138, 133, 10, 121, 24, 215, 36, 333, 38, 407, 4429, 343, 1338, 85, 720, 1023, 420, 105, 118, 2259, 33530, 328, 6250, 1515, 370, 9729, 2059, 825, 6282, 309, 310620, 20089, 10014, 187, 12069, 1101, 21756, 2359, 1253, 53811, 7277, 598, 103772, 1275, 5584, 269

Offset: 1

N. J. A. Sloane, Sep 10 2017

nonn

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.

The empty word is included in the count.

			The following is the analog of columns 3 through 7 of Asveld's Table 1.
1 [171, 6, 56, 59, 138]
2 [166, 6, 56, 59, 133]
3 [11, 6, 16, 17, 10]
4 [154, 6, 56, 59, 121]
5 [105, 0, 0, 31, 24]
6 [14, 518, 28, 85, 215]
7 [57, 6, 38, 41, 36]
8 [68, 518, 42, 85, 333]
9 [173, 0, 0, 49, 38]
10 [1098, 6, 34, 159, 407]
11 [8265, 0, 0, 328, 4429]
12 [720, 6, 34, 93, 343]
13 [1715, 6, 34, 93, 1338]
14 [130, 28, 82, 83, 85]
15 [1979, 6, 20, 215, 720]
16 [2024, 0, 0, 193, 1023]
17 [833, 6, 70, 121, 420]
18 [162, 34, 100, 101, 105]
19 [591, 6, 20, 109, 118]
20 [6124, 0, 0, 357, 2259]
21 [59673, 6, 20, 781, 33530]
22 [748, 0, 0, 150, 328]
23 [11631, 0, 0, 273, 6250]
24 [3200, 6, 56, 261, 1515]
...

Lars Blomberg, Table of n, a(n) for n = 1..6080
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
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]

Cf. A284116, A291067, A291780, A291781.

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.

a(25)-(46) from Lars Blomberg, Sep 14 2017

cp's OEIS Frontend

A284116 a(n) = largest number of distinct words arising in Post's tag system {00, 1101} applied to a binary word w, over all starting words w of length n, or a(n) = -1 if there is a word w with an unbounded trajectory.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A284119 Preperiod (or threshold) of orbit of Post's {00, 1101} tag system applied to the word (100)^n, or -1 if this word has an unbounded trajectory.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A284121 Period of orbit of Post's tag system applied to the word (100)^n (version 1), or -1 if the orbit increases without limit.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A291793 Period of orbit of Post's tag system applied to the word (100)^n (version 2), or -1 if the orbit increases without limit.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A292091 Period of orbit of Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A292090 Preperiod (or threshold) of orbit of Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A292089 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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A292092 Consider Watanabe's 3-shift tag system {00/1011} applied to the word (100)^n; a(n) = length of first word we see that is in the cycle, if the orbit cycles, or 0 if the orbit reaches the empty string, or -1 if the orbit is unbounded.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions