OFFSET
1,5
COMMENTS
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)].
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].
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
LINKS
Sebastian Karlsson, Rows n = 1..13, flattened
D. J. Bernstein and J. C. Lagarias, The 3x+1 conjugacy map, Canadian Journal of Mathematics, Vol. 48, 1996, pp. 1154-1169.
Thijs Laarhoven and Benne de Weger, The Collatz conjecture and De Bruijn graphs, Indagationes Mathematicae. New Series, 24(4) (2013), 971-983. arXiv version, arXiv:1209.3495 [math.NT], 2012.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
FORMULA
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
EXAMPLE
Triangle begins:
n=1 : 0 1;
n=2 : 0 1 2 3;
n=3 : 0 5 2 3 4 1 6 7;
n=4 : 0 5 10 3 4 1 6 7 8 13 2 11 12 9 14 15;
...
A(3, 4) = Sum_{i=0..2} x(i, 4)*2^i = 0*2^0 + 0*2^1 + 1*2^2 = 4.
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.
MATHEMATICA
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 *)
PROG
(Python)
def A014682(k):
if k % 2 == 0:
return k // 2
else:
return (3*k + 1) // 2
def x(i, k):
while i > 0:
k = A014682(k)
i = i - 1
return k % 2
def A(n, k):
L = [x(i, k) * 2**i for i in range(0, n)]
return sum(L)
(PARI) f(n) = if(n%2, 3*n+1, n)/2 \\ A014682
x(i, n) = my(x=n); for (k=1, i, x = f(x)); x % 2;
A(n, k) = sum(i=0, k-1, x(i, n)*2^i);
row(n) = vector(2^n, i, A(i-1, n));
tabf(nn) = for (n=1, nn, print(row(n))); \\ Michel Marcus, Dec 21 2020
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Sebastian Karlsson, Dec 13 2020
STATUS
approved