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

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

N. J. A. Sloane, Aug 18 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.
Up through length 60, all starting strings either reach the empty word or enter a loop. - Don Reble, Sep 01 2017

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

Cf. A291072, A291075, A291780, A291781.

Maple
```
See link.
```

a(8)-(42) from Lars Blomberg, Sep 16 2017

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

Original entry on oeis.org

6, 5, 4, 15, 14, 13, 26, 25, 24, 39, 38, 37, 54, 53, 52, 69, 68, 67, 86, 85, 84, 103, 102, 101, 120, 119, 118, 139, 138, 137, 158, 157, 156, 177, 176, 175, 196, 195, 194, 215, 214, 213, 236, 235, 234, 257, 256, 255, 278, 277

Offset: 1

N. J. A. Sloane, Aug 18 2017

Watanabe's tag system {00, 1110} 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 1110 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 effect 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)

			Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

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

Cf. A291073.

Maple
```
See link.
```

a(8)-(50) from Lars Blomberg, Sep 16 2017

A291072 Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 1011} described in A291067 (but adapted to the alphabet {1,2}) just once.

Original entry on oeis.org

-1, 22, 1, 1, 122, 122, 11, 11, 11, 11, 2122, 2122, 2122, 2122, 111, 211, 111, 211, 111, 211, 111, 211, 12122, 22122, 12122, 22122, 12122, 22122, 12122, 22122, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 1111, 1211, 2111, 2211, 112122, 122122, 212122, 222122

Offset: 1

N. J. A. Sloane, Aug 18 2017

sign

Cf. A007931, A284116, A291067, A291068, A291069.

Cf. also A289673, A291073, A291074.

# First define the mapping by defining the strings T1 and T2:
# Work over the alphabet {1,2}
# 11 / 2212 A284116 This is the "Post Tag System"
T1:="11"; T2:="2212";
# 11 / 2122 A291067 These three are from the Watanabe paper
T1:="11"; T2:="2122";
# 11 / 2221 A291068
T1:="11"; T2:="2221";
# 11 / 1222 A291069
T1:="11"; T2:="1222";
with(StringTools):
# the mapping:
f1:=proc(w) local L, ws, w2; global T1,T2;
ws:=convert(w, string);
if ws="-1" then return("-1"); fi;
if ws[1]="1" then w2:=Join([ws, T1], ""); else w2:=Join([ws, T2], "");  fi;
L:=length(w2); if L <= 3 then return("-1"); fi;
w2[4..L]; end;
# Construct list of words over {1,2} (A007931)
a:= proc(n) local m, r, d; m, r:= n, 0;
      while m>0 do d:= irem(m, 2, 'm');
        if d=0 then d:=2; m:= m-1 fi;
        r:= d, r
      od; parse(cat(r))/10
    end:
WLIST := [seq(a(n), n=1..100)];
# apply the map once:
# this produces A289673, A291072, A291073, A291074
W2:=map(f1,WLIST);

cp's OEIS Frontend

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.

Views

Author

Keywords

Crossrefs

Programs

Maple

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A291072 Take n-th string over {1,2} in lexicographic order and apply the Watanabe tag system {00, 1011} described in A291067 (but adapted to the alphabet {1,2}) just once.

Views

Author

Keywords

Crossrefs

Programs

Maple

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.

Views

Author

Keywords

Crossrefs

Programs

Maple