|
%I #28 May 16 2022 21:13:09
%S 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 26,160,168,170,1024,48,52,53,320,336,340,341,2048,96,17,104,106,640,
%U 672,113,680,682,4096,192,34,208,35,212,213,1280,1344,226,1360,227,1364
%N 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 From _Wolfdieter Lang_, Nov 26 2013: (Start)
%C The length of row (level) l of this table is A005186(l).
%C 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 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 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 The number of vertex labels with CT(l,k) == 4 (mod 6) with l >= 3 is A176866(l+1).
%C 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 T. D. Noe, <a href="/A088975/b088975.txt">Table of n, a(n) for n = 0..3517</a>
%e From _Wolfdieter Lang_, Nov 26 2013: (Start)
%e 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 l\k 1 2 3 4 5 6 7 8 9 10 ...
%e 0: 1
%e 1: 2
%e 2: 4
%e 3: 8
%e 4: (16)
%e 5: 5 | 32
%e 6: (10)|(64)
%e 7: 3 20 | 21 128
%e 8: 6 (40)| 42 (256)
%e 9: 12 13 80 | 84 85 512
%e 10: 24 26 (160) | 168 170 (1024)
%e 11: 48 (52) 53 320 | 336 (340) 341 2048
%e 12: 96 17 104 (106) (640) | 672 113 680 (682) (4096)
%e ...
%e l=13: 192 (34) (208) 35 212 213 1280 | 1344 (226) (1360) 227 1364 1365 8192.
%e l=14: 384 11 68 69 416 (70) (424) 426 (2560) | 2688 75 452 453 2720 (454) (2728) 2730 (16384).
%e 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 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 The alternative Collatz tree, mentioned in a comment above, starts (here the vertex labeled 2 has now out-degree 0):
%e l\k 1 2 3 4 5 6 7 8 ...
%e 0: (4)
%e 1: 1 8
%e 2: 2 (16)
%e 3: 5 32
%e 4: (10) (64)
%e 5: 3 20 21 128
%e 6: 6 (40) 42 (256)
%e 7: 12 13 80 84 85 512
%e 8: 24 26 (160) 168 170 (1024)
%e 9: 48 (52) 53 320 336 (340) 341 2048
%e ... (End)
%o (Python)
%o def A088975():
%o yield 1
%o for x in A088975():
%o if x > 4 and x % 6 == 4:
%o yield (x-1)/3
%o yield 2*x
%Y Cf. A127824 (terms at the same depth are sorted). A005186 (row length), A176866 (number of 4 (mod 6) labels, l >= 3).
%K easy,tabf,nonn
%O 0,2
%A _David Eppstein_, Oct 31 2003
%E Keyword tabf, notation CT(l,k) and two crossrefs added by _Wolfdieter Lang_, Nov 26 2013
|
