A340985 Irregular triangle read by rows: n-th row gives the order of all undirected (also called weakly connected) components of the Collatz digraph of order n, sorted from largest to smallest.

1, 2, 2, 1, 3, 1, 3, 2, 3, 3, 3, 3, 1, 7, 1, 7, 1, 1, 8, 1, 1, 8, 2, 1, 9, 2, 1, 9, 2, 1, 1, 9, 4, 1, 9, 4, 1, 1, 10, 4, 1, 1, 10, 5, 1, 1, 10, 6, 1, 1, 10, 6, 1, 1, 1, 12, 6, 1, 1, 12, 6, 1, 1, 1, 12, 7, 1, 1, 1, 12, 7, 2, 1, 1, 13, 7, 2, 1, 1, 13, 7, 2, 1, 1

Offset: 1

Author

Sebastian Karlsson, Feb 01 2021

Keywords

• nonn
• tabf

Comments

The Collatz digraph of order n is the directed graph with the vertex set V = {1, 2, ..., n} and the arrow set A = {m -> A014682(m) | m and A014682(m) are elements of V}.

Some notes:

- First column is A340010.

- The sum of the n-th row is n - the n-th row can be seen as a partition of n.

- Assuming the Collatz conjecture to be true, the length of each row for n > 1 is A008615(n+7). If the Collatz conjecture is true, then the (infinite) Collatz digraph is an undirected tree except for the cycle 1 -> 2 -> 1. This means that for the Collatz digraph of order n > 1, there will be one undirected component containing the cycle 1 -> 2 -> 1, and precisely one undirected component for every odd k such that 1 < k <= n and (3*k+1)/2 > n. The cardinality of the set {1} U {k | 1 < k <= n, k is odd and (3*k+1)/2 > n} is 1 + floor((n+1)/2) - floor((n+1)/3) = A008615(n+7).

Examples

			+-----------------+  +--------------------------+
|Array begins:    |  | Continues:               |
+-----------------+  +--------------------------+
| 1;              |  | 12, 6, 1, 1, 1;          |
| 2;              |  | 12, 7, 1, 1, 1;          |
| 2,  1;          |  | 12, 7, 2, 1, 1;          |
| 3,  1;          |  | 13, 7, 2, 1, 1;          |
| 3,  2;          |  | 13, 7, 2, 1, 1, 1;       |
| 3,  3;          |  | 21, 2, 1, 1, 1;          |
| 3,  3, 1;       |  | 21, 2, 1, 1, 1, 1;       |
| 7,  1;          |  | 22, 2, 1, 1, 1, 1;       |
| 7,  1, 1;       |  | 22, 2, 2, 1, 1, 1;       |
| 8,  1, 1;       |  | 22, 3, 2, 1, 1, 1;       |
| 8,  2, 1;       |  | 22, 3, 2, 1, 1, 1, 1;    |
| 9,  2, 1;       |  | 24, 3, 2, 1, 1, 1;       |
| 9,  2, 1, 1;    |  | 24, 3, 2, 1, 1, 1, 1;    |
| 9,  4, 1;       |  | 25, 3, 2, 1, 1, 1, 1;    |
| 9,  4, 1, 1;    |  | 25, 4, 2, 1, 1, 1, 1;    |
| 10, 4, 1, 1;    |  | 26, 4, 2, 1, 1, 1, 1;    |
| 10, 5, 1, 1;    |  | 26, 4, 2, 1, 1, 1, 1, 1; |
| 10, 6, 1, 1;    |  | 26, 4, 4, 1, 1, 1, 1;    |
| 10, 6, 1, 1, 1; |  | 26, 4, 4, 1, 1, 1, 1, 1; |
| 12, 6, 1, 1;    |  | 27, 4, 4, 1, 1, 1, 1, 1; |
+-----------------+  +--------------------------+
.
First row is [1] since the Collatz digraph of order 1 is the singleton 1, i.e., there is one weakly connected component which has order 1.
Third row is [2, 1] since the Collatz digraph of order 3 consists of the cycle 1 -> 2 -> 1 and the singleton 3. That gives one weakly connected component of order 2 and one with order 1.
Fifth row is [3, 2] since the Collatz digraph of order 5 consists of the weakly connected components 4 -> 2 -> 1 -> 2 and 3 -> 5. These components have order 3 and 2 respectively.
		

Links

• Sebastian Karlsson, Rows n = 1..400, flattened
• Thijs Laarhoven, The 3n+1 conjecture, Eindhoven University of Technology, Bachelor thesis (2009). See also.
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Cf. A008615, A014682, A088975, A127824, A248573, A340010.

Programs

Python

import networkx as nx
def A014682(n):
    return n//2 if n%2 == 0 else (3*n+1)//2
def Row(n): #Returns n-th row
    G = nx.Graph()
    G.add_nodes_from(range(1, n+1))
    G.add_edges_from([(m,A014682(m)) for m in range(1,n+1) if A014682(m) <= n])
    return sorted([len(c) for c in nx.connected_components(G)], reverse=True)