login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

From Wolfdieter Lang, Nov 26 2013 (Start)

The length of row (level) l of this table is A005186(l).

The (incomplete) ternary sub-tree 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 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 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 sub-tree starting with label 16 at level l=4 is no longer present because the row length A005186(16) = 29 which is odd. (End)

LINKS

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

EXAMPLE

From Wolfdieter Lang, Nov 26 2013 (Start)

In 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 sub-tree 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: replace leading dots by blanks before running)

.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: A225570 A178170 A127824 * A306601 A237851 A167425

Adjacent sequences:  A088972 A088973 A088974 * A088976 A088977 A088978

KEYWORD

easy,tabf,nonn

AUTHOR

David Eppstein, Oct 31 2003

EXTENSIONS

Keyword tabf, notation CT(l,k) and two Cf.s added - Wolfdieter Lang, Nov 26 2013.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 1 22:36 EDT 2021. Contains 346408 sequences. (Running on oeis4.)