cp's OEIS Frontend

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.

%I A339694 #76 Sep 03 2025 13:10:21
%S A339694 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 A339694 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 A339694 27,28,25,30,31,0,21,42,35,20,17,6,23,40,29,34,11
%N 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.
%C A339694 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 A339694 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 A339694 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 A339694 Sebastian Karlsson, <a href="/A339694/b339694.txt">Rows n = 1..13, flattened</a>
%H A339694 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 A339694 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 A339694 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 A339694 J. C. Lagarias, <a href="https://www.jstor.org/stable/2322189">The 3x+1 problem and its generalizations</a>, Amer. Math. Monthly, 92 (1985), 3-23.
%H A339694 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A339694 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 A339694 Triangle begins:
%e A339694 n=1 : 0 1;
%e A339694 n=2 : 0 1  2 3;
%e A339694 n=3 : 0 5  2 3 4 1 6 7;
%e A339694 n=4 : 0 5 10 3 4 1 6 7 8 13 2 11 12 9 14 15;
%e A339694 ...
%e A339694 A(3, 4) = Sum_{i=0..2} x(i, 4)*2^i = 0*2^0 + 0*2^1 + 1*2^2 = 4.
%e A339694 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 A339694 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 A339694 (Python)
%o A339694 def A014682(k):
%o A339694     if k % 2 == 0:
%o A339694         return k // 2
%o A339694     else:
%o A339694         return (3*k + 1) // 2
%o A339694 def x(i, k):
%o A339694     while i > 0:
%o A339694         k = A014682(k)
%o A339694         i = i - 1
%o A339694     return k % 2
%o A339694 def A(n, k):
%o A339694     L = [x(i, k) * 2**i for i in range(0, n)]
%o A339694     return sum(L)
%o A339694 (PARI) f(n) = if(n%2, 3*n+1, n)/2 \\ A014682
%o A339694 x(i, n) = my(x=n); for (k=1, i, x = f(x)); x % 2;
%o A339694 A(n, k) = sum(i=0, k-1, x(i, n)*2^i);
%o A339694 row(n) = vector(2^n, i, A(i-1, n));
%o A339694 tabf(nn) = for (n=1, nn, print(row(n))); \\ _Michel Marcus_, Dec 21 2020
%Y A339694 Cf. A014682, A304715.
%Y A339694 Cf. A000004 (column 0), A052992 (column 1), A263053 (column 2).
%K A339694 nonn,tabf,changed
%O A339694 1,5
%A A339694 _Sebastian Karlsson_, Dec 13 2020