A351849 - OEIS

%I #31 Apr 10 2022 15:33:28

%S 1,11,23,1,111,123,323,3111,11111,11123,12323,32323,323111,3111111,

%T 11111111,11111123,11112323,11232323,23232323,2323231,232311,23111,

%U 1111,1123,2323,231,11,23,1,1111,1123,2323,231,11,23,1

%N 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.

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

%C 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.

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

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

%H Paolo Xausa, <a href="/A351849/b351849.txt">Table of n, a(n) for n = 1..2660 (rows n = 1..26 of triangle, flattened)</a>

%H J. C. Lagarias, <a href="https://arxiv.org/abs/2111.02635">The 3x+1 Problem: An Overview</a>, arXiv:2111.02635 [math.NT], 2021, p. 17.

%H J. C. Lagarias, ed., <a href="http://www.ams.org/bookstore-getitem/item=mbk-78">The Ultimate Challenge: The 3x+1 Problem</a>, American Mathematical Society, 2010, p. 19.

%H Liesbeth De Mol, <a href="https://doi.org/10.1016/j.tcs.2007.10.020">Tag systems and Collatz-like functions</a>, Theoretical Computer Science, Volume 390, Issue 1, 2008, pp. 92-101.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tag_system">Tag system</a>.

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>.

%e Written as an irregular triangle, the sequence begins:

%e       1;

%e      11,    23,     1;

%e     111,   123,   323,  3111,  11111,   11123, ..., 2323, 231, 11, 23, 1;

%e    1111,  1123,  2323,   231,     11,      23,   1;

%e   11111, 11123, 12323, 32323, 323111, 3111111, ...,    1;

%e   ...

%e 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.

%e 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.

%e   111             (corresponding to the integer 3)

%e     123           (appending 23, from production rule 1 -> 23)

%e       323         (appending 23, from production rule 1 -> 23)

%e         3111      (appending 111, from production rule 3 -> 111)

%e           11111   (appending 111, from production rule 3 -> 111)

%e             ...

%e               23  (appending 23, from production rule 1 -> 23)

%e                 1 (appending 1, from production rule 2 -> 1)

%t t[s_]:=StringDrop[s,2]<>StringReplace[StringTake[s,1],{"1"->"23","2"->"1","3"->"111"}];

%t nrows=5;Table[NestWhileList[t,StringRepeat["1",n],#!="1"&],{n,nrows}]

%o (Python)

%o def A351849_row(n):

%o     s = "1" * n

%o     row = [int(s)]

%o     while s != "1":

%o         if s[0] == "1": s += "23"

%o         elif s[0] == "2": s += "1"

%o         else: s += "111"

%o         s = s[2:]

%o         row.append(int(s))

%o     return row

%o nrows = 4

%o print([A351849_row(n) for n in range(1, nrows + 1)])

%Y Cf. A014682, A070168, A351850.

%K nonn,tabf

%O 1,2

%A _Paolo Xausa_, Feb 22 2022