%I #73 Aug 08 2023 14:47:55
%S 0,1,0,1,2,3,0,5,2,3,4,1,6,7,0,5,10,3,4,1,6,7,8,13,2,11,12,9,14,15,0,
%T 21,10,3,20,17,6,23,8,29,2,11,12,9,14,15,16,5,26,19,4,1,22,7,24,13,18,
%U 27,28,25,30,31,0,21,42,35,20,17,6,23,40,29,34,11
%N Triangle read by rows: A(n, k) = Sum_{i=0..n-1} x(i, k)*2^i, where x(i, k) = A014682^(i)(k) (mod 2) using the i-th iteration of A014682.
%C A(n, k) is periodic with period 2^n, i.e., A(n, k) = A(n, k + 2^n). Each row in the triangle is therefore [A(n, 0), A(n, 1), ..., A(n, 2^n-1)].
%C The binary modular Collatz graph C(n) is the graph representing the dynamics of the Collatz function (A014682) modulo 2^n. For example, in C(3), there is an arrow from 3 to 5 and from 3 to 1 because any number that is 3 modulo 8 either gets mapped to 5 modulo 8 or 1 modulo 8. The vertices of the de Bruijn graph B(2,n) are words of length n consisting of the two symbols 0 and 1. If one represents these vertices as integers, b_0 b_1 ... b_{n-1} -> Sum_{i=0..n-1} b_i*2^i, then A(n) : C(n) -> B(2,n) is a graph isomorphism [Laarhoven, de Weger].
%C The n-th row is a permutation on the set {0..2^n-1}. For n > 5, the order of this permutation is 2^(n-4) [Bernstein, Lagarias]. - _Sebastian Karlsson_, Jan 17 2021
%H Sebastian Karlsson, <a href="/A339694/b339694.txt">Rows n = 1..13, flattened</a>
%H D. J. Bernstein and J. C. Lagarias, <a href="https://doi.org/10.4153/CJM-1996-060-x">The 3x+1 conjugacy map</a>, Canadian Journal of Mathematics, Vol. 48, 1996, pp. 1154-1169.
%H Thijs Laarhoven and Benne de Weger, <a href="https://doi.org/10.1016/j.indag.2013.03.003">The Collatz conjecture and De Bruijn graphs</a>, Indagationes Mathematicae. New Series, 24(4) (2013), 971-983. <a href="https://arxiv.org/abs/1209.3495">arXiv version</a>, arXiv:1209.3495 [math.NT], 2012.
%H J. C. Lagarias, <a href="http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html">The 3x+1 problem and its generalizations</a>, Amer. Math. Monthly, 92 (1985), 3-23.
%H J. C. Lagarias, <a href="https://www.maa.org/programs/maa-awards/writing-awards/the-3x-1-problem-and-its-generalizations">The 3x+1 problem and its generalizations</a>, Amer. Math. Monthly, 92 (1985), 3-23.
%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A000120( T(n, (m + 1) mod 2^n) ) = log_3( A014682^n(m + 1 + 2^n) - A014682^n(m + 1) ), m = 0..2^n-1. (A000120 is the binary weight.) - _Thomas Scheuerle_, Aug 23 2021
%e Triangle begins:
%e n=1 : 0 1;
%e n=2 : 0 1 2 3;
%e n=3 : 0 5 2 3 4 1 6 7;
%e n=4 : 0 5 10 3 4 1 6 7 8 13 2 11 12 9 14 15;
%e ...
%e A(3, 4) = Sum_{i=0..2} x(i, 4)*2^i = 0*2^0 + 0*2^1 + 1*2^2 = 4.
%e A(4, 1) = Sum_{i=0..3} x(i, 1)*2^i = 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 = 5.
%t A339694row[n_]:=Table[Sum[Mod[Nest[If[OddQ[#],(3#+1)/2,#/2]&,k,i],2]2^i,{i,0,n-1}],{k,0,2^n-1}];Array[A339694row,6] (* _Paolo Xausa_, Aug 08 2023 *)
%o (Python)
%o def A014682(k):
%o if k % 2 == 0:
%o return k // 2
%o else:
%o return (3*k + 1) // 2
%o def x(i, k):
%o while i > 0:
%o k = A014682(k)
%o i = i - 1
%o return k % 2
%o def A(n, k):
%o L = [x(i, k) * 2**i for i in range(0, n)]
%o return sum(L)
%o (PARI) f(n) = if(n%2, 3*n+1, n)/2 \\ A014682
%o x(i, n) = my(x=n); for (k=1, i, x = f(x)); x % 2;
%o A(n, k) = sum(i=0, k-1, x(i, n)*2^i);
%o row(n) = vector(2^n, i, A(i-1, n));
%o tabf(nn) = for (n=1, nn, print(row(n))); \\ _Michel Marcus_, Dec 21 2020
%Y Cf. A014682, A304715.
%Y Cf. A000004 (column 0), A052992 (column 1), A263053 (column 2).
%K nonn,tabf
%O 1,5
%A _Sebastian Karlsson_, Dec 13 2020