cp's OEIS Frontend

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.

%I A340985 #20 Jan 17 2022 14:01:56
%S A340985 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,
%T A340985 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,
%U A340985 7,1,1,1,12,7,2,1,1,13,7,2,1,1,13,7,2,1,1
%N 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.
%C A340985 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}.
%C A340985 Some notes:
%C A340985 - First column is A340010.
%C A340985 - The sum of the n-th row is n - the n-th row can be seen as a partition of n.
%C A340985 - 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).
%H A340985 Sebastian Karlsson, <a href="/A340985/b340985.txt">Rows n = 1..400, flattened</a>
%H A340985 Thijs Laarhoven, <a href="https://research.tue.nl/en/studentTheses/the-3n-1-conjecture">The 3n+1 conjecture</a>, Eindhoven University of Technology, Bachelor thesis (2009). <a href="http://thijs.com/docs/bsc09-thesis.pdf">See also</a>.
%H A340985 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%e A340985 +-----------------+  +--------------------------+
%e A340985 |Array begins:    |  | Continues:               |
%e A340985 +-----------------+  +--------------------------+
%e A340985 | 1;              |  | 12, 6, 1, 1, 1;          |
%e A340985 | 2;              |  | 12, 7, 1, 1, 1;          |
%e A340985 | 2,  1;          |  | 12, 7, 2, 1, 1;          |
%e A340985 | 3,  1;          |  | 13, 7, 2, 1, 1;          |
%e A340985 | 3,  2;          |  | 13, 7, 2, 1, 1, 1;       |
%e A340985 | 3,  3;          |  | 21, 2, 1, 1, 1;          |
%e A340985 | 3,  3, 1;       |  | 21, 2, 1, 1, 1, 1;       |
%e A340985 | 7,  1;          |  | 22, 2, 1, 1, 1, 1;       |
%e A340985 | 7,  1, 1;       |  | 22, 2, 2, 1, 1, 1;       |
%e A340985 | 8,  1, 1;       |  | 22, 3, 2, 1, 1, 1;       |
%e A340985 | 8,  2, 1;       |  | 22, 3, 2, 1, 1, 1, 1;    |
%e A340985 | 9,  2, 1;       |  | 24, 3, 2, 1, 1, 1;       |
%e A340985 | 9,  2, 1, 1;    |  | 24, 3, 2, 1, 1, 1, 1;    |
%e A340985 | 9,  4, 1;       |  | 25, 3, 2, 1, 1, 1, 1;    |
%e A340985 | 9,  4, 1, 1;    |  | 25, 4, 2, 1, 1, 1, 1;    |
%e A340985 | 10, 4, 1, 1;    |  | 26, 4, 2, 1, 1, 1, 1;    |
%e A340985 | 10, 5, 1, 1;    |  | 26, 4, 2, 1, 1, 1, 1, 1; |
%e A340985 | 10, 6, 1, 1;    |  | 26, 4, 4, 1, 1, 1, 1;    |
%e A340985 | 10, 6, 1, 1, 1; |  | 26, 4, 4, 1, 1, 1, 1, 1; |
%e A340985 | 12, 6, 1, 1;    |  | 27, 4, 4, 1, 1, 1, 1, 1; |
%e A340985 +-----------------+  +--------------------------+
%e A340985 .
%e A340985 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.
%e A340985 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.
%e A340985 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.
%o A340985 (Python)
%o A340985 import networkx as nx
%o A340985 def A014682(n):
%o A340985     return n//2 if n%2 == 0 else (3*n+1)//2
%o A340985 def Row(n): #Returns n-th row
%o A340985     G = nx.Graph()
%o A340985     G.add_nodes_from(range(1, n+1))
%o A340985     G.add_edges_from([(m,A014682(m)) for m in range(1,n+1) if A014682(m) <= n])
%o A340985     return sorted([len(c) for c in nx.connected_components(G)], reverse=True)
%Y A340985 Cf. A008615, A014682, A088975, A127824, A248573, A340010.
%K A340985 nonn,tabf
%O A340985 1,2
%A A340985 _Sebastian Karlsson_, Feb 01 2021