login
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.
14
1, 2, 4, 8, 16, 5, 32, 10, 64, 3, 20, 21, 128, 6, 40, 42, 256, 12, 13, 80, 84, 85, 512, 24, 26, 160, 168, 170, 1024, 48, 52, 53, 320, 336, 340, 341, 2048, 96, 17, 104, 106, 640, 672, 113, 680, 682, 4096, 192, 34, 208, 35, 212, 213, 1280, 1344, 226, 1360, 227, 1364
OFFSET
0,2
COMMENTS
From Wolfdieter Lang, Nov 26 2013: (Start)
The length of row (level) l of this table is A005186(l).
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.
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.
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.
The number of vertex labels with CT(l,k) == 4 (mod 6) with l >= 3 is A176866(l+1).
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)
EXAMPLE
From Wolfdieter Lang, Nov 26 2013: (Start)
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.
l\k 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 2
2: 4
3: 8
4: (16)
5: 5 | 32
6: (10)|(64)
7: 3 20 | 21 128
8: 6 (40)| 42 (256)
9: 12 13 80 | 84 85 512
10: 24 26 (160) | 168 170 (1024)
11: 48 (52) 53 320 | 336 (340) 341 2048
12: 96 17 104 (106) (640) | 672 113 680 (682) (4096)
...
l=13: 192 (34) (208) 35 212 213 1280 | 1344 (226) (1360) 227 1364 1365 8192.
l=14: 384 11 68 69 416 (70) (424) 426 (2560) | 2688 75 452 453 2720 (454) (2728) 2730 (16384).
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.
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.
The alternative Collatz tree, mentioned in a comment above, starts (here the vertex labeled 2 has now out-degree 0):
l\k 1 2 3 4 5 6 7 8 ...
0: (4)
1: 1 8
2: 2 (16)
3: 5 32
4: (10) (64)
5: 3 20 21 128
6: 6 (40) 42 (256)
7: 12 13 80 84 85 512
8: 24 26 (160) 168 170 (1024)
9: 48 (52) 53 320 336 (340) 341 2048
... (End)
PROG
(Python)
def A088975():
yield 1
for x in A088975():
if x > 4 and x % 6 == 4:
yield (x-1)/3
yield 2*x
CROSSREFS
Cf. A127824 (terms at the same depth are sorted). A005186 (row length), A176866 (number of 4 (mod 6) labels, l >= 3).
Sequence in context: A352391 A178170 A127824 * A306601 A237851 A167425
KEYWORD
easy,tabf,nonn
AUTHOR
David Eppstein, Oct 31 2003
EXTENSIONS
Keyword tabf, notation CT(l,k) and two crossrefs added by Wolfdieter Lang, Nov 26 2013
STATUS
approved