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