A351849 Irregular triangle read by rows, in which row n lists the computation of the tag system T_C(3,2) with alphabet {1, 2, 3}, deletion number 2, and production rules 1 -> 23, 2 -> 1, 3 -> 111, when started from the word encoding n.

1, 11, 23, 1, 111, 123, 323, 3111, 11111, 11123, 12323, 32323, 323111, 3111111, 11111111, 11111123, 11112323, 11232323, 23232323, 2323231, 232311, 23111, 1111, 1123, 2323, 231, 11, 23, 1, 1111, 1123, 2323, 231, 11, 23, 1

Offset: 1

Author

Paolo Xausa, Feb 22 2022

Keywords

• nonn
• tabf

Comments

This tag system has no halting symbol: the halting condition is reached when the word 1 is produced.

As proved by De Mol (2008), this tag system encodes the Collatz 3x+1 function T(x), where T(x)=x/2 if x is even, (3x+1)/2 if x is odd.

For each row n >= 1, if the tag system is started from the configuration encoding n (a word composed by n ones), and provided the Collatz conjecture is true, the iterations of the system will always reach the word 1 (after A351850(n) steps).

In her original work De Mol uses the alphabet {alpha, c, y}, which is replaced here by {1, 2, 3}.

Examples

			Written as an irregular triangle, the sequence begins:
      1;
     11,    23,     1;
    111,   123,   323,  3111,  11111,   11123, ..., 2323, 231, 11, 23, 1;
   1111,  1123,  2323,   231,     11,      23,   1;
  11111, 11123, 12323, 32323, 323111, 3111111, ...,    1;
  ...
Each row includes (in the same order of appearance) the words encoding the terms in the corresponding row of A070168. E.g., row 4 includes the words 1111, 11, 1, which encode the numbers 4, 2, 1, respectively.
The following computation shows how row 3 is generated. In each step, symbols coming from the production rules (based on the first symbol of the previous word) are appended; the first two symbols of the word are then deleted.
  111             (corresponding to the integer 3)
    123           (appending 23, from production rule 1 -> 23)
      323         (appending 23, from production rule 1 -> 23)
        3111      (appending 111, from production rule 3 -> 111)
          11111   (appending 111, from production rule 3 -> 111)
            ...
              23  (appending 23, from production rule 1 -> 23)
                1 (appending 1, from production rule 2 -> 1)
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..2660 (rows n = 1..26 of triangle, flattened)
• J. C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021, p. 17.
• J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, American Mathematical Society, 2010, p. 19.
• Liesbeth De Mol, Tag systems and Collatz-like functions, Theoretical Computer Science, Volume 390, Issue 1, 2008, pp. 92-101.
• Wikipedia, Tag system.
• Index entries for sequences related to 3x+1 (or Collatz) problem.

Crossrefs

Cf. A014682, A070168, A351850.

Programs

Mathematica

t[s_]:=StringDrop[s,2]<>StringReplace[StringTake[s,1],{"1"->"23","2"->"1","3"->"111"}];
nrows=5;Table[NestWhileList[t,StringRepeat["1",n],#!="1"&],{n,nrows}]

Python

def A351849_row(n):
    s = "1" * n
    row = [int(s)]
    while s != "1":
        if s[0] == "1": s += "23"
        elif s[0] == "2": s += "1"
        else: s += "111"
        s = s[2:]
        row.append(int(s))
    return row
nrows = 4
print([A351849_row(n) for n in range(1, nrows + 1)])