%I #53 Jan 25 2024 17:15:39
%S 1,2,4,8,5,16,3,10,32,6,20,21,64,12,13,40,42,128,24,26,80,84,85,256,
%T 48,17,52,53,160,168,170,512,96,11,34,104,35,106,320,336,113,340,341,
%U 1024,192,7,22,68,69,208,23,70,212,213,640,672,75,226,680,227,682,2048
%N An irregular triangle giving the Collatz-Terras tree.
%C From _Wolfdieter Lang_, Oct 31 2014: (Start)
%C (old name corrected)
%C Irregular triangle CT(l, m) such that the first three rows l = 0, 1 and 2 are 1, 2, 4, respectively, and for l >= 3 the row entries CT(l, m) are obtained from replacing the numbers of row l-1 by (2*x-1)/3, 2*x if they are 2 (mod 3) and by 2*x otherwise.
%C The modified Collatz (or Collatz-Terras) map sends a positive number x to x/2 if it is even and to (3*x+1)/2 if it is odd (see A060322). The present tree (without the complete tree originating at CT(2,1) = 1) can be considered as an incomplete binary tree, with nodes (vertices) of out-degree 2 if they are 2 (mod 3) and out-degree 1 otherwise. In the example below, the edges (branches) could be labeled L (left) or V (vertical).
%C The row length sequence is A060322(l+1), l>=0. (End)
%C The Collatz conjecture is true if and only if all odd numbers appear in this sequence.
%C This sequence is similar to A127824.
%H Sebastian Karlsson, <a href="/A248573/b248573.txt">Rows l = 0..35, flattened</a>
%H Riho Terras, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf">A stopping time problem on the positive integers</a>, Acta Arith. 30 (1976) 241-252.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>.
%e The irregular triangle CT(l,m) begins:
%e l\m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ...
%e 0: 1
%e 1: 2
%e 2: 4 here the 1, which would generate the complete tree again, is omitted
%e 3: 8
%e 4: 5 16
%e 5: 3 10 32
%e 6: 6 20 21 64
%e 7: 12 13 40 42 128
%e 8: 24 26 80 84 85 256
%e 9: 48 17 52 53 160 168 170 512
%e 10: 96 11 34 104 35 106 320 336 113 340 341 1024
%e 11: 192 7 22 68 69 208 23 70 212 213 640 672 75 226 680 227 682 2048
%e 12: 384 14 44 45 136 138 416 15 46 140 141 424 426 1280 1344 150 452 453 1360 151 454 1364 1365 4096
%e ... reformatted, and extended - _Wolfdieter Lang_, Oct 31 2014
%e --------------------------------------------------------------------------------------------------------------
%e From _Wolfdieter Lang_, Oct 31 2014: (Start)
%e The Collatz-Terras tree starting with 4 looks like (numbers x == 2 (mod 3) are marked with a left bar, and the left branch ends then in (2*x-1)/3 and the vertical one in 2*x)
%e l=2: 4
%e l=3: |8
%e l=4: |5 16
%e l=5: 3 10 |32
%e l=6: 6 |20 21 64
%e l=7: 12 13 40 42 |128
%e l=8: 24 |26 |80 84 85 256
%e l=9: 48 |17 52 |53 160 168 |170 |512
%e l=10: 96 |11 34 |104 |35 106 320 336 |113 340 |341 1024
%e l=11: 192 7 22 |68 69 208 23| 70 212 213 640 672 75 226 680 227 682 2048
%e ...
%e E.g., x = 7 = CT(11, 2) leads back to 4 via 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, and from there back to 2, 1.
%e (End)
%e --------------------------------------------------------------------------------------------------------------
%t Join[{{1}, {2}}, NestList[Flatten[Map[If[Mod[#, 3] == 2, {(2*#-1)/3, 2*#}, 2*#]&, #]]&, {4}, 10]] (* _Paolo Xausa_, Jan 25 2024 *)
%o (PARI) rows(N) = my(r=List(),x); for(i=0, min(2, N), listput(r, x=[2^i])); for(n=3, N, my(w=List()); for(i=1, #x, my(q=2*x[i]); if(1==q%3, listput(w, (q-1)/3)); listput(w, q)); listput(r, x=Vec(w))); Vec(r); \\ _Ruud H.G. van Tol_, Jan 25 2024
%Y Cf. A127824, A060322, A088975.
%K nonn,tabf
%O 0,2
%A _Nico Brown_, Oct 08 2014
%E Edited. New name (old corrected name as comment). - _Wolfdieter Lang_, Oct 31 2014
|