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.

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

Author

David Eppstein, Oct 31 2003

Keywords

• easy
• tabf
• nonn

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)

Examples

			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   [phone]
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)
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..3517

Crossrefs

Cf. A127824 (terms at the same depth are sorted). A005186 (row length), A176866 (number of 4 (mod 6) labels, l >= 3).

Programs

Python

def A088975():
    yield 1
    for x in A088975():
        if x > 4 and x % 6 == 4:
            yield (x-1)/3
        yield 2*x

Extensions

Keyword tabf, notation CT(l,k) and two crossrefs added by Wolfdieter Lang, Nov 26 2013