login
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.
2
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
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.
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
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Feb 22 2022
STATUS
approved