|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
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)
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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)
yield 1
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).
|
|
|
KEYWORD
|
easy,tabf,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Keyword tabf, notation CT(l,k) and two crossrefs added by Wolfdieter Lang, Nov 26 2013
|
|
|
STATUS
|
approved
|
| |
|
|
