cp's OEIS Frontend

A088975 Breadth-first traversal of the Collatz tree, with the odd child of each node traversed prior to its even child. If the Collatz 3n+1 conjecture is true, this is a permutation of all positive integers.

%I A088975 #28 May 16 2022 21:13:09
%S A088975 1,2,4,8,16,5,32,10,64,3,20,21,128,6,40,42,256,12,13,80,84,85,512,24,
%T A088975 26,160,168,170,1024,48,52,53,320,336,340,341,2048,96,17,104,106,640,
%U A088975 672,113,680,682,4096,192,34,208,35,212,213,1280,1344,226,1360,227,1364
%N A088975 Breadth-first traversal of the Collatz tree, with the odd child of each node traversed prior to its even child. If the Collatz 3n+1 conjecture is true, this is a permutation of all positive integers.
%C A088975 From _Wolfdieter Lang_, Nov 26 2013: (Start)
%C A088975 The length of row (level) l of this table is A005186(l).
%C A088975 The (incomplete) ternary subtree starting with the vertex labeled 8 at level l=3 obeys the rules: (i) The three possible edge (branch) labels are L, V, R (for left, vertical and right). (ii) If the vertex label m is congruent to 4 modulo 6 then the out-degree is 2 and the edge labeled L ends in a vertex with label (m-1)/3 and the edge labeled R ends in a vertex with label 2*m. Otherwise (if the vertex label m is congruent to 0, 1, 2, 3, 5 (mod 6)) the out-degree is 1 with the edge labeled V ending in a vertex with label 2*m. See the Python program.
%C A088975 On top of this tree starting with node label 8 one puts the unary tree (out-degree 1) with vertex labels 1, 2, and 4, where each edge label is V. The 1, at level l=0, labels the root of the Collatz tree CT. Note that 4 at level l=2 has out-degree 1 and not 2 even though 4 == 4 (mod 6). This exception is needed because otherwise the L branch would result in a repetition of the whole CT tree.
%C A088975 Alternatively one could start a Collatz tree with vertex label 4 at level 0, using the above given rules, but cut off the L branch originating from 4 after level 2 (out-degree of vertex labeled 2 is 0). Without this cut 4 would appear again and the whole tree would be repeated.
%C A088975 The number of vertex labels with CT(l,k) == 4 (mod 6) with l >= 3 is A176866(l+1).
%C A088975 From level l=16 on the left-right symmetry in the branch structure (forgetting about the vertex labels) of the subtree starting with label 16 at level l=4 is no longer present because the row length A005186(16) = 29, which is odd. (End)
%H A088975 T. D. Noe, <a href="/A088975/b088975.txt">Table of n, a(n) for n = 0..3517</a>
%e A088975 From _Wolfdieter Lang_, Nov 26 2013: (Start)
%e A088975 At the start of table CT the 4 (mod 6) vertex labels CT(l,k) with l >= 4 and out-edges L and R have been put into brackets. The other labels have out-degree 1 with edge label V). A bar separates the left and right subtree originating at vertex 16.
%e A088975 l\k  1    2    3      4     5     6     7    8    9     10 ...
%e A088975 0:   1
%e A088975 1:   2
%e A088975 2:   4
%e A088975 3:   8
%e A088975 4: (16)
%e A088975 5:   5 | 32
%e A088975 6: (10)|(64)
%e A088975 7:   3   20 | 21    128
%e A088975 8:   6  (40)| 42   (256)
%e A088975 9:  12   13   80 |   84    85    512
%e A088975 10: 24   26 (160) | 168   170  (1024)
%e A088975 11: 48  (52)  53    320 | 336   (340) 341 2048
%e A088975 12: 96   17  104   (106) (640) | 672  113  680 (682) (4096)
%e A088975 ...
%e A088975 l=13: 192 (34) (208) 35 212 213 1280 | 1344 (226) (1360) 227 1364 1365 8192.
%e A088975 l=14: 384 11 68 69 416 (70) (424) 426 (2560) | 2688 75 452 453  2720 (454) (2728) 2730 (16384).
%e A088975 l=15: 768 (22) (136) 138 (832) 23 140 141 848 852 853 5120 |  5376 150 (904) 906 (5440) 151 908 909 5456 5460 5461 32768.
%e A088975 At level l=15 the left-right 4 (mod 6) structure becomes for the first time asymmetric. This leads at the next level l=16 to the number of vertices  12+3 | 12+2 = 15|14 in total 29 (odd), breaking the left-right branch symmetry.
%e A088975 The alternative Collatz tree, mentioned in a comment above, starts (here the vertex labeled 2 has now out-degree 0):
%e A088975 l\k  1     2     3      4     5      6     7     8  ...
%e A088975 0:  (4)
%e A088975 1:   1     8
%e A088975 2:   2   (16)
%e A088975 3:   5    32
%e A088975 4:  (10) (64)
%e A088975 5:   3    20    21    128
%e A088975 6:   6   (40)   42   (256)
%e A088975 7:  12    13    80     84    85    512
%e A088975 8:  24    26  (160)   168   170  (1024)
%e A088975 9:  48   (52)   53    320   336   (340)  341  2048
%e A088975 ... (End)
%o A088975 (Python)
%o A088975 def A088975():
%o A088975     yield 1
%o A088975     for x in A088975():
%o A088975         if x > 4 and x % 6 == 4:
%o A088975             yield (x-1)/3
%o A088975         yield 2*x
%Y A088975 Cf. A127824 (terms at the same depth are sorted). A005186 (row length), A176866 (number of 4 (mod 6) labels, l >= 3).
%K A088975 easy,tabf,nonn
%O A088975 0,2
%A A088975 _David Eppstein_, Oct 31 2003
%E A088975 Keyword tabf, notation CT(l,k) and two crossrefs added by _Wolfdieter Lang_, Nov 26 2013