login
Irregular triangle of Terras-modified Collatz problem.
17

%I #36 Mar 19 2021 10:46:28

%S 1,2,1,3,5,8,4,2,1,4,2,1,5,8,4,2,1,6,3,5,8,4,2,1,7,11,17,26,13,20,10,

%T 5,8,4,2,1,8,4,2,1,9,14,7,11,17,26,13,20,10,5,8,4,2,1,10,5,8,4,2,1,11,

%U 17,26,13,20,10,5,8,4,2,1,12,6,3,5,8,4,2,1,13,20,10,5,8,4,2,1,14,7,11

%N Irregular triangle of Terras-modified Collatz problem.

%C The row length of this irregular triangle is A006666(n) + 1 = A064433(n+1), n >= 1. - _Wolfdieter Lang_, Mar 20 2014

%H Reinhard Zumkeller, <a href="/A070168/b070168.txt">Rows n = 1..250 of triangle, flattened</a>

%H J. C. Lagarias, <a href="http://www.jstor.org/stable/2322189">The 3x+1 Problem and its Generalizations</a>, Amer. Math. Monthly 92 (1985) 3-23.

%H R. Terras, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf">A stopping time problem on the positive integers</a>, Acta Arith. 30 (1976) 241-252.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>

%F From _Wolfdieter Lang_, Mar 20 2014: (Start)

%F See Lagarias, pp. 4-7, eqs. (2.1), (2.4) with (2.5) and (2.6).

%F T(n,k) = T^{(k)}(n), with the iterations of the Terras-modified Collatz map: T(n) = n/2 if n is even and otherwise (3*n+1)/2, n >= 1. T^{(0)}(n) = n.

%F T(n,k) = lambda(n,k)*n + rho(n,k), with lambda(n,k) = (3^X(n,k,-1))/2^k and rho(n,k) = sum(x(n,j)*(3^X(n,k,j))/ 2^(k-j), j=0..(k-1)) with X(n,k,j) = sum(x(n,j+p), p=1.. (k-1-j)) where x(n,j) = T^{(j)}(n) (mod 2). The parity sequence suffices to determine T(n,k).

%F (End)

%e The irregular triangle begins:

%e n\k 0 1 2 3 4 5 6 8 9 10 11 12 13 14 ...

%e 1: 1

%e 2: 2 1

%e 3: 3 5 8 4 2 1

%e 4: 4 2 1

%e 5: 5 8 4 2 1

%e 6: 6 3 5 8 4 2 1

%e 7: 7 11 17 26 13 20 10 5 8 4 2 1

%e 8: 8 4 2 1

%e 9: 9 14 7 11 17 26 13 20 10 5 8 4 2 1

%e 10: 10 5 8 4 2 1

%e 11: 11 17 26 13 20 10 5 8 4 2 1

%e 12: 12 6 3 5 8 4 2 1

%e 13: 13 20 10 5 8 4 2 1

%e 14: 14 7 11 17 26 13 20 10 5 8 4 2 1

%e 15: 15 23 35 53 80 40 20 10 5 8 4 2 1

%e ... formatted by _Wolfdieter Lang_, Mar 20 2014

%e -------------------------------------------------------------

%t f[n_] := If[EvenQ[n], n/2, (3 n + 1)/2];

%t Table[NestWhileList[f, n, # != 1 &], {n, 1, 30}] // Grid (* _Geoffrey Critzer_, Oct 18 2014 *)

%o (Haskell)

%o a070168 n k = a070168_tabf !! (n-1) !! (k-1)

%o a070168_tabf = map a070168_row [1..]

%o a070168_row n = (takeWhile (/= 1) $ iterate a014682 n) ++ [1]

%o a070168_list = concat a070168_tabf

%o -- _Reinhard Zumkeller_, Oct 03 2014

%o (Python)

%o def a(n):

%o if n==1: return [1]

%o l=[n, ]

%o while True:

%o if n%2==0: n//=2

%o else: n = (3*n + 1)//2

%o l.append(n)

%o if n<2: break

%o return l

%o for n in range(1, 16): print(a(n)) # _Indranil Ghosh_, Apr 15 2017

%Y Cf. A070165 (ordinary Collatz case).

%Y Cf. A014682, A248573, A285098 (row sums).

%K nonn,easy,tabf

%O 1,2

%A _Eric W. Weisstein_, Apr 23 2002

%E Name shortened, tabl changed into tabf, Cf. added by _Wolfdieter Lang_, Mar 20 2014