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

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, 22, 22, 22, 24, 24, 25, 25, 26, 26, 26, 26, 27, 27, 28, 28, 33, 33, 33, 33, 34, 34, 36, 36, 37, 37, 37, 37, 39, 39, 40, 40, 40, 40, 40, 40, 41, 41, 42, 42, 44, 44

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

References

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.

Links

Sebastian Karlsson, Table of n, a(n) for n = 1..20000

Lorenzo Sauras Altuzarra, Some arithmetical problems that are obtained by analyzing proofs and infinite graphs, arXiv:2002.03075 [math.NT], 2020.

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

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

Prog

(Python)
import networkx as nx
def T(n): #A014682
    return n//2 if n%2 == 0 else (3*n+1)//2
def a(n):
    G = nx.Graph()
    G.add_nodes_from(range(1, n+1))
    G.add_edges_from([(m, T(m)) for m in range(1, n+1) if T(m) <= n])
    return len(max(nx.connected_components(G)))
for n in range(1, 70):
    print(a(n), end=", ")

Crossrefs

Cf. A006370, A014682, A127824, A248573, A088975, A008615, A103469.

Cf. A340985.

Sequence in context: A239496 A348164 A299962 * A128586 A130971 A051776

Adjacent sequences: A340007 A340008 A340009 * A340011 A340012 A340013

Keyword

nonn

Author

Sebastian Karlsson, Dec 26 2020

Status

approved