A351850 a(n) is the number of iterations of the computation of the A351849 tag system when started from the word encoding n, or -1 if the number of iterations is infinite.

0, 2, 24, 6, 20, 30, 128, 14, 152, 30, 120, 42, 64, 142, 300, 30, 108, 170, 236, 50, 84, 142, 284, 66, 300, 90, 40656, 170, 216, 330, 40524, 62, 384, 142, 260, 206, 264, 274, 996, 90, 40628, 126, 596, 186, 256, 330, 40492, 114, 388, 350, 520, 142, 224, 40710

Offset: 1

Author

Paolo Xausa, Feb 22 2022

Keywords

• nonn

Comments

If x is even, the A351849 tag system evolves from the word encoding x to the word encoding x/2 in x iterations; if x is odd, x+1 iterations are required to produce the word encoding (3x+1)/2.

See A351849 for additional comments, links and examples.

Examples

			When started from 1111 (the word encoding the number 4), the system evolves as 1111 -> 1123 -> 2323 -> 231 -> 11 -> 23 -> 1, reaching the word 1 after 6 steps. a(4) is therefore 6.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• Liesbeth De Mol, Tag systems and Collatz-like functions, Theoretical Computer Science, Volume 390, Issue 1, 2008, pp. 92-101.
• Index entries for sequences related to 3x+1 (or Collatz) problem.

Crossrefs

Cf. A006666, A070168, A285098, A351849.

Programs

Mathematica

(* First program, based on the tag system definition *)
t[s_]:=StringDrop[s,2]<>StringReplace[StringTake[s,1],{"1"->"23","2"->"1","3"->"111"}];
nterms=100;Table[Length[NestWhileList[t,StringRepeat["1",n],#!="1"&]]-1,{n,nterms}]
(* Second program, more efficient, based on formula *)
c[x_]:=If[OddQ[x],(3x+1)/2,x/2];
nterms=100;Table[Total[Map[If[OddQ[#],#+1,#]&,NestWhileList[c,n,#>1&]]]-2,{n,nterms}]

Python

def A351850(n):
    s, steps = "1" * n, 0
    while s != "1":
        if s[0] == "1": s += "23"
        elif s[0] == "2": s += "1"
        else: s += "111"
        s = s[2:]
        steps += 1
    return steps
nterms = 100
print([A351850(n) for n in range(1, nterms + 1)])

Formula

a(n) = (Sum_{k=0..A006666(n)} 2*floor((A070168(n,k)+1)/2)) - 2.