%I #62 Aug 04 2024 11:16:12
%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,17,96,104,106,113,
%U 640,672,680,682,4096,34,35,192,208,212,213,226,227,1280,1344,1360,1364
%N Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.
%C The length of each row is A005186(n). The largest number in row n is 2^n. The second-largest number in row n is A000975(n-2) for n>4. The smallest number in row n is A033491(n). The Collatz conjecture asserts that every positive integer occurs in some row of this triangle.
%C n is an element of row number A006577(n). - _Reinhard Zumkeller_, Oct 03 2012
%C Conjecture: The numbers T(n, 1),...,T(n, k_n) of row n are arranged in non-overlapping clusters of numbers which have the same order of magnitude and whose Collatz trajectories to 1 have the same numbers of ups and downs. The highest cluster of row n is just the number 2^n, the trajectory to 1 of which has n-1 downs and no ups. The second highest cluster of row n consists of the numbers T(n, k_n - r) = 4^(r - 1) * t(n - 2*r + 2) for 1 <= r <= (n - 3) / 2, where t(k) = (2^k - (-1)^k - 3) / 6. These have n-2 downs and one up. The largest and second largest number of this latter cluster are given by A000975 and A153772. - _Markus Sigg_, Sep 25 2020
%D See also A006577.
%H Alois P. Heinz, <a href="/A127824/b127824.txt">Rows n = 0..42, flattened</a> (first 31 rows from T. D. Noe)
%H Paul Andaloro, <a href="http://www.fq.math.ca/Scanned/38-1/andaloro.pdf">On total stopping times under 3x+1 iteration</a>, Fib. Quar. 38 (1) (2000) 73.
%H Jason Davies, <a href="https://www.jasondavies.com/collatz-graph/">Collatz Graph: All Numbers Lead to One</a>
%H Wolfdieter Lang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Lang/lang6.html">On Collatz Words, Sequences, and Trees</a>, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
%H Markus Sigg, <a href="https://arxiv.org/abs/2012.07839">On the cluster structures in Collatz preimages</a>, arXiv:2012.07839 [math.GM], 2020.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a>
%F Suppose S is the list of numbers in row n. Then the list of numbers in row n+1 is the union of each number in S multiplied by 2 and the numbers (x-1)/3, where x is in S, with x=1 (mod 3) and where (x-1)/3 is an odd number greater than 1.
%e The triangle starts:
%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: 17 96 104 106 113 640 672 680 682 4096
%e - _Reinhard Zumkeller_, Oct 03 2012
%t s={1}; t=Flatten[Join[s, Table[s=Union[2s, (Select[s,Mod[ #,3]==1 && OddQ[(#-1)/3] && (#-1)/3>1&]-1)/3]; s, {n,13}]]]
%o (Haskell)
%o import Data.List (union, sort)
%o a127824 n k = a127824_tabf !! n !! k
%o a127824_row n = a127824_tabf !! n
%o a127824_tabf = iterate f [1] where
%o f row = sort $ map (* 2) row `union`
%o [x' | x <- row, let x' = (x - 1) `div` 3,
%o x' * 3 == x - 1, odd x', x' > 1]
%o -- _Reinhard Zumkeller_, Oct 03 2012
%Y Cf. A006577 (total stopping time of n), A088975 (traversal of the Collatz tree).
%Y Column k=1 gives A033491.
%Y Last elements of rows give A000079.
%Y Row lengths give A005186.
%Y Row sums give A337673(n+1).
%K nice,nonn,tabf,look,changed
%O 0,2
%A _T. D. Noe_, Jan 31 2007
|