A291796 -id:A291796 - 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)

A291792 Numbers m such that Post's tag system started at the word (100)^m eventually dies (i.e., reaches the empty string).

Original entry on oeis.org

5, 13, 14, 22, 25, 46, 47, 54, 63, 65, 70, 74, 78, 80, 91, 93, 106, 110, 117, 118, 128, 144, 148, 160, 166, 169, 190, 195, 199, 209, 222, 229, 234, 236, 239, 240, 243, 252, 254, 263, 264, 265, 266, 278, 281, 283, 286, 302, 304, 310, 324, 326, 327, 336, 339

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

These are the numbers m such that A291793(m)=0, or equivalently A284121(m)=1.
Comments from Lars Blomberg on the method used in calculating the terms, Sep 14 2017: (Start)
Here is an overview of the method I have been using.
Build the words in a large byte array. Each iteration just adds 00 or 1101 to the end and removes 3 bytes from the beginning, without moving the whole word, just keeping track of the length of the word and where it starts within the array.
When the word reaches the end of the array it is moved to the beginning. This allows for very fast iterations, as long as the word is substantially shorter than the array.
The size of the byte array is 10^9, this is the longest word we can handle.
As for cycle detection, the words at iterations A: k*10^5 and B: (k+1)*10^5 are saved.
For iterations above B when the current word has the same length as B (a fast test), then check if the current word is equal to the one at B. If so, we have a cycle whose length can be determined simply by continued iterating. When the current iteration reaches C: (k+2)*10^5, move B->A, C->B, and continue.
The cycle has started somewhere between A and B and we know the cycle length. So restart two iterations at A and initially iterate one of them by the cycle length. Then iterate the two in parallel (being a cycle length apart) until they are equal, which gives the start of the cycle. Only the two words being iterated need to be stored.
One drawback with this method is that it cannot detect a cycle longer than 10^5 (or whatever value we choose). In that case the iterations will go on forever.
(End)
The trajectory of the word (100)^m for m=110 dies after 43913328040672 iterations, so 110 is a term in this sequence. The longest word in the trajectory is 31299218, which appeared at iteration 14392308412264. - Lars Blomberg, Oct 04 2017

Lars Blomberg, Table of n, a(n) for n = 1..1100
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
N. J. A. Sloane, Maple code for A291792, A284119, A291793, A284121, A291794, A291795, A291796, A292089, A292090, A292091, A292092, A292093, A292094.
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part 1, Part 2, Slides. (Mentions this sequence)
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, A284121, A291793.

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)-a(17) from Lars Blomberg, Sep 08 2017

a(18)-a(55) from Lars Blomberg, Oct 15 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

A291802 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

Original entry on oeis.org

0, 3, 0, 0, 16, 14, 0, 0, 0, 13, 15, 11, 23, 9, 0, 18, 0, 22, 20, 0, 12, 8, 24, 10, 20, 18, 2, 6, 106, 16, 0, 23, 27, 0, 0, 0, 27, 5, 25, 0, 0, 105, 3, 103, 37, 15, 1, 1, 107, 17, 19, 101, 9, 99, 2, 35, 7, 7, 31, 13, 71, 97, 0, 0, 0, 0, 0, 22, 0, 34, 0, 0, 0

Offset: 1

N. J. A. Sloane, Sep 04 2017

nonn

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.
We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.
This is an analog of A291796 for the words in A291797.

Lars Blomberg, Table of n, a(n) for n = 1..8190 (For terms in A291797 up to length 36.)
Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102. See Table 3.

Cf. A284116, A291794, A291795, A291796, A291797.

a(31)-a(73) from Lars Blomberg, Sep 08 2017

A346040 a(n) is 1w' converted to decimal, where the binary word w' is the result of applying Post's tag system {00,1101} to the binary word w, where 1w is n converted to binary (the leftmost 1 acts as a delimiter).

Original entry on oeis.org

1, 1, 5, 2, 2, 13, 13, 4, 4, 4, 4, 29, 29, 29, 29, 8, 12, 8, 12, 8, 12, 8, 12, 45, 61, 45, 61, 45, 61, 45, 61, 16, 20, 24, 28, 16, 20, 24, 28, 16, 20, 24, 28, 16, 20, 24, 28, 77, 93, 109, 125, 77, 93, 109, 125, 77, 93, 109, 125, 77, 93, 109, 125, 32, 36, 40

Offset: 1

Carlos Gómez-Ambrosi, Jul 02 2021

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.
It is an important open question to decide whether there is any word whose orbit grows without limit.
Note that there is a one-to-one correspondence between positive integers and binary words (including the empty word), given by n (decimal) = 1w (binary) -> w.
With alphabet {0,1} replaced by {1,2}, the above correspondence is given by A007931, and a step of the tag system by A289673.
The present sequence allows for looking into Post's tag system "numerically", instead of "combinatorially".

			n = 22 (decimal) = 10110 (binary) = 1w ->
                w = 0110 ->
                    011000 ->
                  w' = 000 ->
                1w' = 1000 (binary) = 8 (decimal) = a(22)
n = 25 (decimal) = 11001 (binary) = 1w ->
                w = 1001 ->
                    10011101 ->
                  w' = 11101 ->
                1w' = 111101 (binary) = 61 (decimal) = a(25)

Carlos Gómez-Ambrosi, Table of n, a(n) for n = 1..10000
Liesbeth De Mol, Tracing unsolvability: a mathematical, historical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, University of Ghent, 2007. See also.
Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197-215. See also. Post's tag system {00,1101} appears on page 204.

Cf. A289673 (alphabet 1,2).

Cf. A284116, A284119, A284121, A289670, A289671, A289672, A289674, A289675, A291792, A291793, A291794, A291795, A291796, A291798, A291799, A291800, A291801, A291802, A337537.

function m = A346040(n)
if n == 1
    m = 1;
else
    s = dec2bin(n);
    if strcmp(s(2),'0')
        t = [s '00'];
    else
        t = [s '1101'];
    end
    t(2) = [];
    t(2) = [];
    t(2) = [];
    m = bin2dec(t);
end
end

a(n) = if(n==1,1, my(k=logint(n,2)); if(bittest(n,k-1), n=n<<4+13;k++, n<<=2;k--); bitand(n,bitneg(0,k)) + 1<Kevin Ryde, Jul 02 2021

def a(n):
    if n == 1:
        return 1
    else:
        s = n.digits(2)
        s.reverse()
        if s[1] == 0:
            t = s + [0,0]
        else:
            t = s + [1,1,0,1]
        del(t[1])
        del(t[1])
        del(t[1])
        return sum(t[k]*2^(len(t)-1-k) for k in srange(0,len(t)))

a(n) = delete(append(n)), where:
append(1) = 1;
append(n) = 2^(2 + 2 * floor((n - 2^k)/2^(k-1))) * n + 13 * floor((n - 2^k)/2^(k-1)) if n > 1, where k = floor(log_2(n));
delete(n) = n + 2^t * (1 - floor(n/2^t)), where t = max(floor(log_2(n))-3,0).
In the expression for append(n), floor((n - 2^k)/2^(k-1)) is the second-highest bit in the binary expansion of n, which is A079944, with offset 2.

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

A291792 Numbers m such that Post's tag system started at the word (100)^m eventually dies (i.e., reaches the empty string).

Views

Author

Keywords

Comments

Links

Crossrefs

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A291802 Take n-th word over {1,2} listed in A291797 and apply the Post tag system described in A284116 (but adapted to the alphabet {1,2}); a(n) = position of the longest word in the orbit, or -1 if the orbit is unbounded.

Views

Author

Keywords