cp's OEIS Frontend

A340010 The order of the largest weakly connected component of the Collatz digraph of order n.

%I A340010 #28 Feb 20 2021 03:42:58
%S A340010 1,2,2,3,3,3,3,7,7,8,8,9,9,9,9,10,10,10,10,12,12,12,12,13,13,21,21,22,
%T A340010 22,22,22,24,24,25,25,26,26,26,26,27,27,28,28,33,33,33,33,34,34,36,36,
%U A340010 37,37,37,37,39,39,40,40,40,40,40,40,41,41,42,42,44,44
%N A340010 The order of the largest weakly connected component of the Collatz digraph of order n.
%C A340010 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}.
%D A340010 J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
%H A340010 Sebastian Karlsson, <a href="/A340010/b340010.txt">Table of n, a(n) for n = 1..20000</a>
%H A340010 Lorenzo Sauras Altuzarra, <a href="https://arxiv.org/abs/2002.03075">Some arithmetical problems that are obtained by analyzing proofs and infinite graphs</a>, arXiv:2002.03075 [math.NT], 2020.
%H A340010 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 A340010 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%e A340010 The weakly connected components of the Collatz digraph of order 3 are 1 -> 2 -> 1 and the singleton 3. The order of the largest component is #{1, 2} = 2.
%e A340010 The weakly connected components of the Collatz digraph of order 10 correspond to the following partition of {1, 2, ..., 10}: {1, 2, 3, 4, 5, 6, 8, 10}, {7} and {9}. The order of the largest component is #{1, 2, 3, 4, 5, 6, 8, 10} = 8. Hence, a(10) = 8.
%e A340010 The weakly connected components of the Collatz digraph of order 20 correspond to the partition {1, 2, 3, 4, 5, 6, 8, 10, 12, 13, 16, 20}, {7, 9, 11, 14, 17, 18}, {15} and {19}. The order of the largest component is #{1, 2, 3, 4, 5, 6, 8, 10, 12, 13, 16, 20} = 12. Thus, a(20) = 12.
%o A340010 (Python)
%o A340010 import networkx as nx
%o A340010 def T(n): #A014682
%o A340010     return n//2 if n%2 == 0 else (3*n+1)//2
%o A340010 def a(n):
%o A340010     G = nx.Graph()
%o A340010     G.add_nodes_from(range(1, n+1))
%o A340010     G.add_edges_from([(m,T(m)) for m in range(1, n+1) if T(m) <= n])
%o A340010     return len(max(nx.connected_components(G)))
%o A340010 for n in range(1, 70):
%o A340010     print(a(n), end=", ")
%Y A340010 Cf. A006370, A014682, A127824, A248573, A088975, A008615, A103469.
%Y A340010 Cf. A340985.
%K A340010 nonn
%O A340010 1,2
%A A340010 _Sebastian Karlsson_, Dec 26 2020