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,2

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).

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

Example

+-----------------+  +--------------------------+
|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.

Prog

(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)

Crossrefs

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

Sequence in context: A206441 A175245 A167413 * A259176 A237591 A359979

Adjacent sequences: A340982 A340983 A340984 * A340986 A340987 A340988

Keyword

nonn,tabf

Author

Sebastian Karlsson, Feb 01 2021

Status

approved