A127824 Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.

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, 17, 96, 104, 106, 113, 640, 672, 680, 682, 4096, 34, 35, 192, 208, 212, 213, 226, 227, 1280, 1344, 1360, 1364

Offset: 0

Author

T. D. Noe, Jan 31 2007

Keywords

• nice
• nonn
• tabf
• look

Comments

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.

n is an element of row number A006577(n). - Reinhard Zumkeller, Oct 03 2012

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

Examples

			The triangle starts:
   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:  17   96  104  106  113  640  672  680  682 4096
- _Reinhard Zumkeller_, Oct 03 2012
		

References

• See also A006577.

Links

• Alois P. Heinz, Rows n = 0..42, flattened (first 31 rows from T. D. Noe)
• Paul Andaloro, On total stopping times under 3x+1 iteration, Fib. Quar. 38 (1) (2000) 73.
• Jason Davies, Collatz Graph: All Numbers Lead to One
• Wolfdieter Lang, On Collatz Words, Sequences, and Trees, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
• Markus Sigg, On the cluster structures in Collatz preimages, arXiv:2012.07839 [math.GM], 2020.
• Wikipedia, Collatz Conjecture

Crossrefs

Cf. A006577 (total stopping time of n), A088975 (traversal of the Collatz tree).

Column k=1 gives A033491.

Last elements of rows give A000079.

Row lengths give A005186.

Row sums give A337673(n+1).

Programs

Haskell

import Data.List (union, sort)
a127824 n k = a127824_tabf !! n !! k
a127824_row n = a127824_tabf !! n
a127824_tabf = iterate f [1] where
   f row = sort $ map (* 2) row `union`
                  [x' | x <- row, let x' = (x - 1) `div` 3,
                        x' * 3 == x - 1, odd x', x' > 1]
-- Reinhard Zumkeller, Oct 03 2012

Mathematica

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}]]]

Formula

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.