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,2

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

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.

Example

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)

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}]

Prog

(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)])

Crossrefs

Cf. A014682, A070168, A351850.

Sequence in context: A345404 A225186 A155973 * A253684 A364165 A180481

Adjacent sequences: A351846 A351847 A351848 * A351850 A351851 A351852

Keyword

nonn,tabf

Author

Paolo Xausa, Feb 22 2022

Status

approved