login
This site is supported by donations to The OEIS 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. 8
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    9    10 ...

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

l\k  1     2     3      4     5      6     7     8  ...

... (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 * A237851 A167425 A212638

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 04:27 EDT 2017. Contains 292403 sequences.