A340010 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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=", ")