A339694 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.

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, 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, 27, 28, 25, 30, 31, 0, 21, 42, 35, 20, 17, 6, 23, 40, 29, 34, 11

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.

Index entries for sequences related to 3x+1 (or Collatz) problem

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

Cf. A014682, A304715.

Cf. A000004 (column 0), A052992 (column 1), A263053 (column 2).

Sequence in context: A072594 A353051 A272591 * A074722 A370744 A331102

Adjacent sequences: A339691 A339692 A339693 * A339695 A339696 A339697

Keyword

nonn,tabf

Author

Sebastian Karlsson, Dec 13 2020

Status

approved