login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
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 (list; graph; refs; listen; history; text; internal format)
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.

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: A071322 A072594 A272591 * A074722 A331102 A080368

Adjacent sequences:  A339691 A339692 A339693 * A339695 A339696 A339697

KEYWORD

nonn,tabf

AUTHOR

Sebastian Karlsson, Dec 13 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 27 06:18 EST 2022. Contains 350601 sequences. (Running on oeis4.)