A248573 -id:A248573 - cp's OEIS frontend

A070168 Irregular triangle of Terras-modified Collatz problem.

1, 2, 1, 3, 5, 8, 4, 2, 1, 4, 2, 1, 5, 8, 4, 2, 1, 6, 3, 5, 8, 4, 2, 1, 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 8, 4, 2, 1, 9, 14, 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 10, 5, 8, 4, 2, 1, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 12, 6, 3, 5, 8, 4, 2, 1, 13, 20, 10, 5, 8, 4, 2, 1, 14, 7, 11

Offset: 1

Eric W. Weisstein, Apr 23 2002

The row length of this irregular triangle is A006666(n) + 1 = A064433(n+1), n >= 1. - Wolfdieter Lang, Mar 20 2014

			The irregular triangle begins:
n\k   0   1   2   3   4   5   6   8  9 10  11  12  13  14 ...
1:    1
2:    2   1
3:    3   5   8   4   2   1
4:    4   2   1
5:    5   8   4   2   1
6:    6   3   5   8   4   2   1
7:    7  11  17  26  13  20  10   5  8  4   2   1
8:    8   4   2   1
9:    9  14   7  11  17  26  13  20 10  5   8   4   2   1
10:  10   5   8   4   2   1
11:  11  17  26  13  20  10   5   8  4  2   1
12:  12   6   3   5   8   4   2   1
13:  13  20  10   5   8   4   2   1
14:  14   7  11  17  26  13  20  10  5  8   4   2   1
15:  15  23  35  53  80  40  20  10  5  8   4   2   1
...  formatted by _Wolfdieter Lang_, Mar 20 2014
-------------------------------------------------------------

Reinhard Zumkeller, Rows n = 1..250 of triangle, flattened
J. C. Lagarias, The 3x+1 Problem and its Generalizations, Amer. Math. Monthly 92 (1985) 3-23.
R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976) 241-252.
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture

Cf. A070165 (ordinary Collatz case).

Cf. A014682, A248573, A285098 (row sums).

a070168 n k = a070168_tabf !! (n-1) !! (k-1)
a070168_tabf = map a070168_row [1..]
a070168_row n = (takeWhile (/= 1) $ iterate a014682 n) ++ [1]
a070168_list = concat a070168_tabf
-- Reinhard Zumkeller, Oct 03 2014

f[n_] := If[EvenQ[n], n/2, (3 n + 1)/2];
Table[NestWhileList[f, n, # != 1 &], {n, 1, 30}] // Grid (* Geoffrey Critzer, Oct 18 2014 *)

def a(n):
    if n==1: return [1]
    l=[n, ]
    while True:
        if n%2==0: n//=2
        else: n = (3*n + 1)//2
        l.append(n)
        if n<2: break
    return l
for n in range(1, 16): print(a(n)) # Indranil Ghosh, Apr 15 2017

From Wolfdieter Lang, Mar 20 2014: (Start)
See Lagarias, pp. 4-7, eqs. (2.1), (2.4) with (2.5) and (2.6).
T(n,k) = T^{(k)}(n), with the iterations of the Terras-modified Collatz map: T(n) = n/2 if n is even and otherwise (3*n+1)/2, n >= 1. T^{(0)}(n) = n.
T(n,k) = lambda(n,k)*n + rho(n,k), with lambda(n,k) = (3^X(n,k,-1))/2^k and rho(n,k) = sum(x(n,j)*(3^X(n,k,j))/ 2^(k-j), j=0..(k-1)) with X(n,k,j) = sum(x(n,j+p), p=1.. (k-1-j)) where x(n,j) = T^{(j)}(n) (mod 2). The parity sequence suffices to determine T(n,k).
(End)

Name shortened, tabl changed into tabf, Cf. added by Wolfdieter Lang, Mar 20 2014

A131450 a(n) is the number of integers x that can be written x = (2^c(1) - 2^c(2) - 32^c(3) - 3^22^c(4) - ... - 3^(m-2)*2^c(m) - 3^(m-1)) / 3^m for integers c(1), c(2), ..., c(m) such that n = c(1) > c(2) > ... > c(m) > 0 and c(1) - c(2) != 2 if m >= 2.

Original entry on oeis.org

0, 1, 0, 1, 1, 1, 1, 1, 2, 4, 6, 6, 7, 8, 11, 18, 23, 29, 39, 52, 71, 99, 124, 160, 220, 302, 403, 532, 707, 936, 1249, 1668, 2220, 2976, 3966, 5278, 7028, 9386, 12531, 16696, 22246, 29622, 39540, 52768, 70395, 93795, 124977, 166619, 222222, 296358, 395213

Offset: 1

Perry Dobbie, Jul 11 2007, Jul 12 2007, Jul 13 2007, Jul 17 2007, Jul 22 2007, Oct 15 2008

nonn

For m = 1, the expression for x becomes x = (2^c(1) - 1) / 3.
Also the number of odd x with stopping time n for the Collatz or 3x+1 problem where x->x/2 if x is even, x->(3x+1)/2 if x is odd (see A060322), except that 1 is counted as having stopping time 2 instead of 0.
Equivalently, a(n) is the number of x == 2 (mod 3) with stopping time n-1.
The number of possible c(1),...,c(m) is 2^(n-1) - 2^(n-3); most do not yield integer x.
n-c(m), n-c(m-1), ..., n-c(2) are the stopping times of the odd integers in the Collatz trajectory of x.
For n > 4, a(n) = a(n-2) + a(n-2):(x is 1 mod 6) + a(n-1):(x is 5 mod 6). [I.e., for n > 4, a(n) = a(n-2) + (number of values of x counted in a(n-2) such that x == 1 (mod 6)) + (number of values of x counted in a(n-1) such that x == 5 (mod 6)). - Jon E. Schoenfield, Mar 14 2022]
It is conjectured that lim_{n->oo} a(n)/a(n-1) = 4/3.
With a(2) = 0 this is the first difference sequence of A060322, the row length sequence of A248573 (Collatz-Terras tree). - Wolfdieter Lang, May 04 2015
From Jon E. Schoenfield, Mar 15 2022: (Start)
For n > 4, the set of integers counted in a(n) is the union of three disjoint sets:
(1) the set of integers 4*x+1 obtained using all integers x counted by a(n-2),
(2) the set of integers (4*x-1)/3 obtained using only those integers x counted by a(n-2) that satisfy x == 1 (mod 6), and
(3) the set of integers (2*x-1)/3 obtained using only those integers x counted by a(n-1) that satisfy x == 5 (mod 6). (See Example.) (End)

			For n=3, the only valid c are:
  c = (3,2,1): (2^3 - 2^2 - 3^1*2^1 - 3^2) / 3^3 = -11/27,
  c = (3,2):   (2^3 - 2^2 - 3^1) / 3^2 = 1/9,
  c = (3):     (2^3 - 2^0) / 3 = 7/3,
  and none are integers so a(3) = 0.
a(9)=2:
  c = (9,5):   (2^9 - 2^5 - 3) / 3 = 53,
  c = (9,5,2): (2^9 - 2^5 - 3*2^2 - 9) / 27 = 17,
  and no other valid c give integer x.
From _Jon E. Schoenfield_, Mar 15 2022: (Start)
The a(12)=6 integers x are { 15, 45, 141, 151, 453, 1365 }, of which only one (151) satisfies x == 1 (mod 6);
the a(13)=7 integers x are { 9, 29, 93, 277, 301, 853, 909 }, of which only one (29) satisfies x == 5 (mod 6);
thus, at n=14, the set of a(14)=8 integers is the union of the three sets
  { 4*15+1 = 61, 4*45+1 = 181, 4*141+1 = 565, 4*151+1 = 605, 4*453+1 = 1813, 4*1365+1 = 5461 },
  { (4*151-1)/3 = 201 }, and
  { (2*29-1)/3 = 19 }. (End)

Perry Dobbie, Collatz representations.
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A060322, A248573.

a:=[0,1,0,1]; Y:=[]; X:=[5]; for n in [5..51] do Z:=Y; Y:=X; X:=[]; for x in Z do X[#X+1]:=4*x+1; end for; for x in Z do if x mod 6 eq 1 then X[#X+1]:=(4*x-1) div 3; end if; end for; for x in Y do if x mod 6 eq 5 then X[#X+1]:=(2*x-1) div 3; end if; end for; X:=Sort(X); a[n]:=#X; end for; a; // Jon E. Schoenfield, Mar 15 2022

Edited by David Applegate, Oct 16 2008

a(51) from Jon E. Schoenfield, Mar 15 2022

A060322 Consider the version of the Collatz or 3x+1 problem where x -> x/2 if x is even, x -> (3x+1)/2 if x is odd. Define the stopping time of x to be the number of steps needed to reach 1. Sequence gives the number of integers x with stopping time n.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 12, 18, 24, 31, 39, 50, 68, 91, 120, 159, 211, 282, 381, 505, 665, 885, 1187, 1590, 2122, 2829, 3765, 5014, 6682, 8902, 11878, 15844, 21122, 28150, 37536, 50067, 66763, 89009, 118631, 158171, 210939, 281334, 375129, 500106, 666725

Offset: 1

Bo T. Ahlander (ahlboa(AT)isk.kth.se), Mar 29 2001

nonn

The Mathematica function StoppingTime[n] is the length of the Collatz sequence starting at n before reaching 1.
Suppose we have a list L of the numbers with StoppingTime n. Then the list LL of StoppingTime n+1 can be produced as: First. Add to LL all numbers in L multiplied by 2. Second. For the numbers x now in LL, if x == 1 (mod 3), AppendTo LL the number (x-1)/3 (if (x-1)/3 != 1). These two steps make LL complete.
I think the offset, examples, formula and code are all off by 1 -- they all treat the stopping time of 1 to be 1, rather than 0. - David Applegate, Oct 16 2008
a(n+1), n >= 0, is the row length of A248573(n,m) (Collatz-Terras tree). For the first differences see A131450(n+1), but with A131450(2) = 1 (the number of 2 (mod 3) numbers in row n, for n >= 0, of A248573). - Wolfdieter Lang, May 04 2015

			StoppingTime = 1: L = {1}, a(1)=1.
StoppingTime = 2: L = {2}, a(2)=1.
StoppingTime = 3: L = {4}, a(3)=1.
StoppingTime = 4: L = {8}, a(4)=1.
StoppingTime = 5: L = {5, 16}, a(5)=2. First, LL = {10, 32} (= 2*L). Second, 10 == 1 (mod 3), so we AppendTo LL also (10-1)/3 = 3. We get LL = {3, 10, 32}. So a(6) = 3.

See A005186 for another version.

Cf. A248573, A131450.

(*** Program #1 ***) For[v = 1, v <= 12, v++, lst = {}; For[n = 1, n < 2^v, n++, If[StoppingTime[n] == v, AppendTo[lst, n]]]; Print[lst]; Print[Length[lst]]; ]
(*** Program #2 ***) lst1 = {1}; For[v = 1, v <= 12, v++, L1 = Length[lst1]; Print["Number of numbers with StoppingTime ", v, ": ", L1]; Print["List of numbers: ", lst1]; (* Numbers with StoppingTime n *) Print["Control of StoppingTime: ", Map[StoppingTime, lst1]]; (* Controll *) Print[""]; lst2 = 2 lst1; For[i = 1, i <= L1, i++, x = (lst2[[i]] - 1)/3; If[IntegerQ[x] && x != 1, AppendTo[lst2, x]]; ]; lst1 = Sort[lst2]; ]
(*** Program #3 ***) lst0 = {}; lst1 = {1}; For[v = 1, v <= 35, v++, L1 = Length[lst1]; AppendTo[lst0, L1]; lst2 = 2 lst1; For[i = 1, i <= L1, i++, x = (lst2[[i]] - 1)/3; If[IntegerQ[x], AppendTo[lst2, x]]; ]; lst1 = Complement[lst2, {1}]; ]; lst0

first(N) = my(a=Vec([1, 1, 1, 1, 2], N), p=[], q=[5]); for(n=6, N, my(r=List()); foreach(p, x, listput(r, 4*x+1); if(1==x%6, listput(r, x+(x-1)/3))); foreach(q, x, if(5==x%6, listput(r, x-(x+1)/3))); a[n]=a[n-1]+#r; p=q; q=Vec(r)); a; \\ Ruud H.G. van Tol, Aug 14 2024

# code to calculate terms after a(4):
@x=(8,0);for($n=5;$n<=60;$n++){do{$q=2*shift(@x);push(@x,($q-1)/3)if($q%3==1);push @x,$q}while $q;print($#x,", ");} # Carl R. White, Oct 03 2006

Conjecture: lim_{n->oo} a(n) = a(n-1)*4/3. - Joe Slater, Jan 27 2024

More terms from Carl R. White, Oct 03 2006
Edited by N. J. A. Sloane, Sep 15 2007
More terms from Joe Slater, Apr 10 2025

A324246 Irregular triangle T read by rows: T(n, k) = (A324038(n, k) - 1)/2.

Original entry on oeis.org

0, 2, 1, 10, 6, 42, 8, 26, 56, 170, 5, 34, 17, 106, 37, 226, 113, 682, 3, 22, 138, 11, 70, 426, 150, 906, 75, 454, 2730, 4, 14, 90, 184, 554, 7, 46, 282, 568, 1706, 200, 602, 1208, 3626, 100, 302, 1818, 3640, 10922, 18, 9, 58, 120, 362, 738, 369, 2218, 30, 186, 376, 1130, 2274, 1137, 6826, 133, 802, 401, 2410, 805, 4834, 2417, 14506, 402, 201, 1210, 2424, 7274, 14562, 7281, 43690

Offset: 0

Nicolas Vaillant, Philippe Delarue, Wolfdieter Lang, May 09 2019

The length of row n is A324039, for n >= 0.
This is the incomplete binary tree corresponding to the modified Collatz map f (from the Vaillant and Delarue link) given in A324245.
The branches of this tree, called CfTree, give the iterations under the Vaillant and Delarue map f of the vertex labels of level n until label 0 on level n = 0 is reached.
The out-degree of a vertex label T(n, k), for n >= 1, is 1 if T(n, k) == 1 (mod 3) and 2 for all other labels. For level n = 0 with vertex label 0 this rule does not hold, it has out-degree 1, not 2.
The number of vertex labels on level n which are 1 (mod 3) is given in A324040.
The corresponding tree CfsTree with only odd vertex labels t(n, k) = 2*T(n,k) + 1 is given in A324038.
The Collatz conjecture is that all nonnegative integers appear in this CfTree. Because the sets of labels on the levels are pairwise disjoint, these numbers will then appear just once.
For this tree see Figure 2 in the Vaillant-Delarue link. It is also shown in the W. Lang link given in A324038.

			The irregular triangle T begins (the brackets combine pairs coming from out-degree 2 vertices of the preceding level):
----------------------------------------------------------
n\k   1  2    3   4     5    6     7   8   9  10    11 ...
0:    0
1:    2
2:   (1 10)
3:    6 42
4:   (8 26) (56 170)
5:   (5 34) (17 106)  (37  226) (113 682)
6:   (3 22) 138 (11    70) 426   150 906 (75 454) 2730
...
Row n = 7: (4 14) 90 (184 554)  (7 46) 282 (568 1706) (200 602) (1208 3626) (100 302) 1818 (3640 10922);
Row n = 8: 18 (9 58) (120 362) 738 (369 2218) 30 186 (376 1130) 2274 (1137 6826) (133 802) (401 2410) (805 4834) (2417 14506) 402 (201 1210) (2424 7274) 14562 (7281 43690).
...
The successors of T(1,1) = 2 == 2 (mod 3) are (-1 + 2*2 )/3 = 1 and 2*(1 + 2*2) = 10. The successor of T(2, 1) = 1  == 1 (mod 3) is 2*(1 + 2*1) = 6. The successors of T(3, 1) = 6  == 0 (mod 3) are 4*6/3 = 8 and 2*(1 + 2*6) = 26.

Nicolas Vaillant and Philippe Delarue, The hidden face of the 3x+1 problem. Part I: Intrinsic algorithm, April 26 2019.

Cf. A248573 (Collatz-Terras tree), A324038 (CfsTree), A324039, A324040, A324245.

Recurrence for the set of vertex labels CfTree(n) = {T(n, k), k = 1..A324039(n)} on level (row) n:
  This set is obtained, with the map f from A324245, from CfTree(0) = {0}, CfTree(1) = {2}, and for n >= 2 CfTree(n) = {m >= 0: f(m) = T(n-1, k), for k = 1.. A324039(n-1)}.
Explicit form for the successor of T(n, k) on row (level) n+1, for n >= 1:
a label with T(n, k) == 1 (mod 3) produces the label 2*(1 + 2*T(n, k)) on row n+1; label T(n, k) == 0 (mod 3) produces the two labels 4*T(n, k)/3 and 2*(1 + 2*T(n, k)); label T(n, k) == 2 (mod 3) produces the two labels (-1 + 2*T(n, k))/3 and 2*(1 + 2*T(n, k)).

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.

Original entry on oeis.org

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

Sebastian Karlsson, Feb 01 2021

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

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

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

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

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)

A304715 For any n > 0, if A006666(n) >= 0, then a(n) = Sum_{i = 0..A006666(n)-1} 2^i * [T^i(n) == 0 (mod 2)] (where [] is an Iverson bracket and T^i denotes the i-th iterate of the Collatz function A014682); otherwise a(n) = -1.

Original entry on oeis.org

0, 1, 28, 3, 14, 57, 1896, 7, 7586, 29, 948, 115, 118, 3793, 3824, 15, 474, 15173, 15180, 59, 62, 1897, 1912, 231, 60722, 237, 1102691417057682138372, 7587, 7590, 7649, 137836427132210267296, 31, 242890, 949, 956, 30347, 30350, 30361, 7772616, 119

Offset: 1

Rémy Sigrist, May 17 2018

In other words, when a(n) >= 0, the binary representation of a(n) encodes the tripling and halvings steps of the Collatz compressed trajectory of n up to the first occurrence of the number 1 (where zeros and ones respectively denote tripling and halving steps).

			The first terms, alongside the binary representation of a(n) and the Collatz compressed trajectory of a(n) up to the first 1 in reverse order, are:
  n    a(n)       bin(a(n))  rev(traj(n))
  --   ----       ---------  ------------
   1      0               0  (1)
   2      1               1  (1, 2)
   3     28           11100  (1, 2, 4, 8, 5, 3)
   4      3              11  (1, 2, 4)
   5     14            1110  (1, 2, 4, 8, 5)
   6     57          111001  (1, 2, 4, 8, 5, 3, 6)
   7   1896     11101101000  (1, 2, 4, 8, 5, 10, 20, 13, 26, 17, 11, 7)
   8      7             111  (1, 2, 4, 8)
   9   7586   1110110100010  (1, 2, 4, 8, 5, 10, 20, 13, 26, 17, 11, 7, 14, 9)
  10     29           11101  (1, 2, 4, 8, 5, 10)
  11    948      1110110100  (1, 2, 4, 8, 5, 10, 20, 13, 26, 17, 11)
  12    115         1110011  (1, 2, 4, 8, 5, 3, 6, 12)
  13    118         1110110  (1, 2, 4, 8, 5, 10, 20, 13)
  14   3793    111011010001  (1, 2, 4, 8, 5, 10, 20, 13, 26, 17, 11, 7, 14)
  15   3824    111011110000  (1, 2, 4, 8, 5, 10, 20, 40, 80, 53, 35, 23, 15)
  16     15            1111  (1, 2, 4, 8, 16)
  17    474       111011010  (1, 2, 4, 8, 5, 10, 20, 13, 26, 17)
  18  15173  11101101000101  (1, 2, 4, 8, 5, 10, 20, 13, 26, 17, 11, 7, 14, 9, 18)

Cf. A000120, A006666, A014682, A029837, A220071, A248573.

a(n) = my (v=0); for (k=0, oo, if (n==1, return (v), n%2, n = (3*n+1)/2, n = n/2; v += 2^k))

a(2^k) = 2^k - 1 for any k >= 0.
a(2*n) = 2*a(n) + 1.
A029837(a(n)+1) = A006666(n).
A000120(a(n)) = A220071(n).
a(A248573(n)) < a(A248573(n+1)) for any n >= 0. - Rémy Sigrist, Nov 09 2018

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

Original entry on oeis.org

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

Sebastian Karlsson, Dec 26 2020

nonn

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

			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.

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

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

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

Cf. A340985.

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

cp's OEIS Frontend

A070168 Irregular triangle of Terras-modified Collatz problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A131450 a(n) is the number of integers x that can be written x = (2^c(1) - 2^c(2) - 3*2^c(3) - 3^2*2^c(4) - ... - 3^(m-2)*2^c(m) - 3^(m-1)) / 3^m for integers c(1), c(2), ..., c(m) such that n = c(1) > c(2) > ... > c(m) > 0 and c(1) - c(2) != 2 if m >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Extensions

A060322 Consider the version of the Collatz or 3x+1 problem where x -> x/2 if x is even, x -> (3x+1)/2 if x is odd. Define the stopping time of x to be the number of steps needed to reach 1. Sequence gives the number of integers x with stopping time n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Formula

Extensions

A324246 Irregular triangle T read by rows: T(n, k) = (A324038(n, k) - 1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A304715 For any n > 0, if A006666(n) >= 0, then a(n) = Sum_{i = 0..A006666(n)-1} 2^i * [T^i(n) == 0 (mod 2)] (where [] is an Iverson bracket and T^i denotes the i-th iterate of the Collatz function A014682); otherwise a(n) = -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

A131450 a(n) is the number of integers x that can be written x = (2^c(1) - 2^c(2) - 32^c(3) - 3^22^c(4) - ... - 3^(m-2)*2^c(m) - 3^(m-1)) / 3^m for integers c(1), c(2), ..., c(m) such that n = c(1) > c(2) > ... > c(m) > 0 and c(1) - c(2) != 2 if m >= 2.