A088975 -id:A088975 - cp's OEIS frontend

A343280 a(n) is the number of steps for the n-th vertex of the Collatz tree A088975 to reach a vertex t == 0 (mod 3).

7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0, 7, 6, 0, 5, 2, 0, 3, 4, 0

Offset: 1

Heinz Ebert, Apr 10 2021

The terminal node t == 0 (mod 3) can be computed by repeated application of the operation m'=2m until n*(2^(a(n)-1)) == 10 (mod 18) is valid; then application of the operation m'=(m-1)/3 results in t = (n*(2^(a(n)-1))-1)/3. Both operations are part of the inverse Collatz function. The sequence repeats after every n == 0 (mod 9) thus:
  t = ((2^6)*(9k+1)-1)/3 = (18k*(2^5)+63)/3=192k+21 -> t == 0(mod 3),
  t = ((2^5)*(9k+2)-1)/3 = (18k*(2^4)+63)/3=96k+21  -> t == 0(mod 3),
  t = 9k+3 -> t == 0(mod 3),
  t = ((2^4)*(9k+4)-1)/3 = (18k*(2^3)+63)/3=48k+21  -> t == 0(mod 3),
  t = ((2^1)*(9k+5)-1)/3 = (18k+9)/3=6k+3           -> t == 0(mod 3),
  t = 9k+6 -> t == 0(mod 3),
  t = ((2^2)*(9k+7)-1)/3 = (18k*2+27)/3=12k+9       -> t == 0(mod 3),
  t = ((2^3)*(9k+8)-1)/3 = (18k*(2^2)+63)/3=24k+21  -> t == 0(mod 3),
  t = 9k -> t == 0(mod 3).
There are three additional facts according to the sequence:
1. The sequence is based on the proof of S. Andrei et al. (see LINKS) that at most 7 steps are needed to reach a multiple of 3.
2. The distance 1 is missing due to the fact that all y == 10 (mod 18) are congruent to 1 modulo 9. Obviously for every positive integer y == 10 (mod 18) the distance to the next level is 1 not 7, since ((18k+10)-1)/3 = 6k+3. Thus repeating the proof with all rest classes modulo 18 includes the distance 1 but blows up the sequence to: 7, 6, 0, 5, 2, 0, 3, 4, 0, 1, 6, 0, 5, 2, 0, 3, 4, 0 but without touching the previous fact.
3. Another consequence is that there exists a path P from every positive integer n as a start terminal of P to an end terminal t == 0 (mod 3). Thus every path P is unique because of the unique start node n but the map t = (n*(2^(a(n)-1))-1)/3 is surjective.

Stefan Andrei, Manfred Kudlek, and Radu Stefan Niculescu, Chains in Collatz's tree, Report 217, 1999, Dep. of Informatics, University of Hamburg.
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,1).

Cf. A088975, A006370.

Function a(n As Long)
  Dim d As Long, k As Long
  d = 0
  If ((n Mod 3) <> 0) Then
    k = n
    Do
      d = d + 1: k = k + k
    Loop Until ((k Mod 9) = 1)
    d = d + 1
  End If
  a = d
End Function

G.f.: -x*(4*x^7 + 3*x^6 + 2*x^4 + 5*x^3 + 6*x + 7)/(x^9 - 1). - Thomas Scheuerle, Apr 12 2021

A007310 Numbers congruent to 1 or 5 mod 6.

Original entry on oeis.org

1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175

Offset: 1

C. Christofferson (Magpie56(AT)aol.com)

Numbers n such that phi(4n) = phi(3n). - Benoit Cloitre, Aug 06 2003
Or, numbers relatively prime to 2 and 3, or coprime to 6, or having only prime factors >= 5; also known as 5-rough numbers. (Edited by M. F. Hasler, Nov 01 2014: merged with comments from Zak Seidov, Apr 26 2007 and Michael B. Porter, Oct 09 2009)
Apart from initial term(s), dimension of the space of weight 2n cuspidal newforms for Gamma_0( 38 ).
Numbers k such that k mod 2 = 1 and (k+1) mod 3 <> 1. - Klaus Brockhaus, Jun 15 2004
Also numbers n such that the sum of the squares of the first n integers is divisible by n, or A000330(n) = n*(n+1)*(2*n+1)/6 is divisible by n. - Alexander Adamchuk, Jan 04 2007
Numbers n such that the sum of squares of n consecutive integers is divisible by n, because A000330(m+n) - A000330(m) = n*(n+1)*(2*n+1)/6 + n*(m^2+n*m+m) is divisible by n independent of m. - Kaupo Palo, Dec 10 2016
A126759(a(n)) = n + 1. - Reinhard Zumkeller, Jun 16 2008
Terms of this sequence (starting from the second term) are equal to the result of the expression sqrt(4!*(k+1) + 1) - but only when this expression yields integral values (that is when the parameter k takes values, which are terms of A144065). - Alexander R. Povolotsky, Sep 09 2008
For n > 1: a(n) is prime if and only if A075743(n-2) = 1; a(2*n-1) = A016969(n-1), a(2*n) = A016921(n-1). - Reinhard Zumkeller, Oct 02 2008
A156543 is a subsequence. - Reinhard Zumkeller, Feb 10 2009
Numbers n such that ChebyshevT(x, x/2) is not an integer (is integer/2). - Artur Jasinski, Feb 13 2010
If 12*k + 1 is a perfect square (k = 0, 2, 4, 10, 14, 24, 30, 44, ... = A152749) then the square root of 12*k + 1 = a(n). - Gary Detlefs, Feb 22 2010
A089128(a(n)) = 1. Complement of A047229(n+1) for n >= 1. See A164576 for corresponding values A175485(a(n)). - Jaroslav Krizek, May 28 2010
Cf. property described by Gary Detlefs in A113801 and in Comment: more generally, these numbers are of the form (2*h*n+(h-4)*(-1)^n-h)/4 (with h, n natural numbers), therefore ((2*h*n+(h-4)*(-1)^n-h)/4)^2-1 == 0 (mod h); in this case, a(n)^2 - 1 == 0 (mod 6). Also a(n)^2 - 1 == 0 (mod 12). - Bruno Berselli, Nov 05 2010 - Nov 17 2010
Numbers n such that ( Sum_{k = 1..n} k^14 ) mod n = 0. (Conjectured) - Gary Detlefs, Dec 27 2011
From Peter Bala, May 02 2018: (Start)
The above conjecture is true. Apply Ireland and Rosen, Proposition 15.2.2. with m = 14 to obtain the congruence 6*( Sum_{k = 1..n} k^14 )/n = 7 (mod n), true for all n >= 1.  Suppose n is coprime to 6, then 6 is a unit in Z/nZ, and it follows from the congruence that ( Sum_{k = 1..n} k^14 )/n is an integer. On the other hand, if either 2 divides n or 3 divides n then the congruence shows that ( Sum_{k = 1..n} k^14 )/n cannot be integral. (End)
A126759(a(n)) = n and A126759(m) < n for m < a(n). - Reinhard Zumkeller, May 23 2013
(a(n-1)^2 - 1)/24 = A001318(n), the generalized pentagonal numbers. - Richard R. Forberg, May 30 2013
Numbers k for which A001580(k) is divisible by 3. - Bruno Berselli, Jun 18 2014
Numbers n such that sigma(n) + sigma(2n) = sigma(3n). - Jahangeer Kholdi and Farideh Firoozbakht, Aug 15 2014
a(n) are values of k such that Sum_{m = 1..k-1} m*(k-m)/k is an integer. Sums for those k are given by A062717. Also see Detlefs formula below based on A062717. - Richard R. Forberg, Feb 16 2015
a(n) are exactly those positive integers m such that the sequence b(n) = n*(n + m)*(n + 2*m)/6 is integral, and also such that the sequence c(n) = n*(n + m)*(n + 2*m)*(n + 3*m)/24 is integral. Cf. A007775. - Peter Bala, Nov 13 2015
Along with 2, these are the numbers k such that the k-th Fibonacci number is coprime to every Lucas number. - Clark Kimberling, Jun 21 2016
This sequence is the Engel expansion of 1F2(1; 5/6, 7/6; 1/36) + 1F2(1; 7/6, 11/6; 1/36)/5. - Benedict W. J. Irwin, Dec 16 2016
The sequence a(n), n >= 4 is generated by the successor of the pair of polygonal numbers {P_s(4) + 1, P_(2*s - 1)(3) + 1}, s >= 3. - Ralf Steiner, May 25 2018
The asymptotic density of this sequence is 1/3. - Amiram Eldar, Oct 18 2020
Also, the only vertices in the odd Collatz tree A088975 that are branch values to other odd nodes t == 1 (mod 2) of A005408. - Heinz Ebert, Apr 14 2021
From Flávio V. Fernandes, Aug 01 2021: (Start)
For any two terms j and k, the product j*k is also a term (the same property as p^n and smooth numbers).
From a(2) to a(phi(A033845(n))), or a((A033845(n))/3), the terms are the totatives of the A033845(n) itself. (End)
Also orders n for which cyclic and semicyclic diagonal Latin squares exist (see A123565 and A342990). - Eduard I. Vatutin, Jul 11 2023
If k is in the sequence, then k*2^m + 3 is also in the sequence, for all m > 0. - Jules Beauchamp, Aug 29 2024

			G.f. = x + 5*x^2 + 7*x^3 + 11*x^4 + 13*x^5 + 17*x^6 + 19*x^7 + 23*x^8 + ...

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1980.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Andreas Enge, William Hart, and Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], 2016-2018.
B. W. J. Irwin, Constants Whose Engel Expansions are the k-rough Numbers.
L. B. W. Jolley, Summation of Series, Dover, 1961
Cedric A. B. Smith, Prime factors and recurring duodecimals, Math. Gaz. 59 (408) (1975) 106-109.
William A. Stein's The Modular Forms Database, PARI-readable dimension tables for Gamma_0(N).
Eric Weisstein's World of Mathematics, Rough Number.
Eric Weisstein's World of Mathematics, Pi Formulas. [_Jaume Oliver Lafont_, Oct 23 2009]
Index entries for sequences related to smooth numbers [_Michael B. Porter_, Oct 09 2009]
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

A005408 \ A016945. Union of A016921 and A016969; union of A038509 and A140475. Essentially the same as A038179. Complement of A047229. Subsequence of A186422.
Cf. A000330, A001580, A002194, A019670, A032528 (partial sums), A038509 (subsequence of composites), A047209, A047336, A047522, A056020, A084967, A090771, A091998, A144065, A175885-A175887.
For k-rough numbers with other values of k, see A000027, A005408, A007775, A008364-A008366, A166061, A166063.
Cf. A126760 (a left inverse).
Row 3 of A260717 (without the initial 1).
Cf. A105397 (first differences).

Filtered([1..150],n->n mod 6=1 or n mod 6=5); # Muniru A Asiru, Dec 19 2018

a007310 n = a007310_list !! (n-1)
a007310_list = 1 : 5 : map (+ 6) a007310_list
-- Reinhard Zumkeller, Jan 07 2012

[n: n in [1..250] | n mod 6 in [1, 5]]; // Vincenzo Librandi, Feb 12 2016

seq(seq(6*i+j,j=[1,5]),i=0..100); # Robert Israel, Sep 08 2014

Select[Range[200], MemberQ[{1, 5}, Mod[#, 6]] &] (* Harvey P. Dale, Aug 27 2013 *)
a[n_] := (6 n + (-1)^n - 3)/2; a[rem156, 60] (* Robert G. Wilson v, May 26 2014 from a suggestion by N. J. A. Sloane *)
Flatten[Table[6n + {1, 5}, {n, 0, 24}]] (* Alonso del Arte, Feb 06 2016 *)
Table[2*Floor[3*n/2] - 1, {n, 1000}] (* Mikk Heidemaa, Feb 11 2016 *)

isA007310(n) = gcd(n,6)==1 \\ Michael B. Porter, Oct 09 2009

A007310(n)=n\2*6-(-1)^n \\ M. F. Hasler, Oct 31 2014

\\ given an element from the sequence, find the next term in the sequence.
nxt(n) = n + 9/2 - (n%6)/2 \\ David A. Corneth, Nov 01 2016

def A007310(n): return (n+(n>>1)<<1)-1 # Chai Wah Wu, Oct 10 2023

[i for i in range(150) if gcd(6,i) == 1] # Zerinvary Lajos, Apr 21 2009

a(n) = (6*n + (-1)^n - 3)/2. - Antonio Esposito, Jan 18 2002
a(n) = a(n-1) + a(n-2) - a(n-3), n >= 4. - Roger L. Bagula
a(n) = 3*n - 1 - (n mod 2). - Zak Seidov, Jan 18 2006
a(1) = 1 then alternatively add 4 and 2. a(1) = 1, a(n) = a(n-1) + 3 + (-1)^n. - Zak Seidov, Mar 25 2006
1 + 1/5^2 + 1/7^2 + 1/11^2 + ... = Pi^2/9 [Jolley]. - Gary W. Adamson, Dec 20 2006
For n >= 3 a(n) = a(n-2) + 6. - Zak Seidov, Apr 18 2007
From R. J. Mathar, May 23 2008: (Start)
Expand (x+x^5)/(1-x^6) = x + x^5 + x^7 + x^11 + x^13 + ...
O.g.f.: x*(1+4*x+x^2)/((1+x)*(1-x)^2). (End)
a(n) = 6*floor(n/2) - 1 + 2*(n mod 2). - Reinhard Zumkeller, Oct 02 2008
1 + 1/5 - 1/7 - 1/11 + + - - ... = Pi/3 = A019670 [Jolley eq (315)]. - Jaume Oliver Lafont, Oct 23 2009
a(n) = ( 6*A062717(n)+1 )^(1/2). - Gary Detlefs, Feb 22 2010
a(n) = 6*A000217(n-1) + 1 - 2*Sum_{i=1..n-1} a(i), with n > 1. - Bruno Berselli, Nov 05 2010
a(n) = 6*n - a(n-1) - 6 for n>1, a(1) = 1. - Vincenzo Librandi, Nov 18 2010
Sum_{n >= 1} (-1)^(n+1)/a(n) = A093766 [Jolley eq (84)]. - R. J. Mathar, Mar 24 2011
a(n) = 6*floor(n/2) + (-1)^(n+1). - Gary Detlefs, Dec 29 2011
a(n) = 3*n + ((n+1) mod 2) - 2. - Gary Detlefs, Jan 08 2012
a(n) = 2*n + 1 + 2*floor((n-2)/2) = 2*n - 1 + 2*floor(n/2), leading to the o.g.f. given by R. J. Mathar above. - Wolfdieter Lang, Jan 20 2012
1 - 1/5 + 1/7 - 1/11 + - ... = Pi*sqrt(3)/6 = A093766 (L. Euler). - Philippe Deléham, Mar 09 2013
1 - 1/5^3 + 1/7^3 - 1/11^3 + - ... = Pi^3*sqrt(3)/54 (L. Euler). - Philippe Deléham, Mar 09 2013
gcd(a(n), 6) = 1. - Reinhard Zumkeller, Nov 14 2013
a(n) = sqrt(6*n*(3*n + (-1)^n - 3)-3*(-1)^n + 5)/sqrt(2). - Alexander R. Povolotsky, May 16 2014
a(n) = 3*n + 6/(9*n mod 6 - 6). - Mikk Heidemaa, Feb 05 2016
From Mikk Heidemaa, Feb 11 2016: (Start)
a(n) = 2*floor(3*n/2) - 1.
a(n) = A047238(n+1) - 1. (suggested by Michel Marcus) (End)
E.g.f.: (2 + (6*x - 3)*exp(x) + exp(-x))/2. - Ilya Gutkovskiy, Jun 18 2016
From Bruno Berselli, Apr 27 2017: (Start)
a(k*n) = k*a(n) + (4*k + (-1)^k - 3)/2 for k>0 and odd n, a(k*n) = k*a(n) + k - 1 for even n. Some special cases:
k=2: a(2*n) = 2*a(n) + 3 for odd n, a(2*n) = 2*a(n) + 1 for even n;
k=3: a(3*n) = 3*a(n) + 4 for odd n, a(3*n) = 3*a(n) + 2 for even n;
k=4: a(4*n) = 4*a(n) + 7 for odd n, a(4*n) = 4*a(n) + 3 for even n;
k=5: a(5*n) = 5*a(n) + 8 for odd n, a(5*n) = 5*a(n) + 4 for even n, etc. (End)
From Antti Karttunen, May 20 2017: (Start)
a(A273669(n)) = 5*a(n) = A084967(n).
a((5*n)-3) = A255413(n).
A126760(a(n)) = n. (End)
a(2*m) = 6*m - 1, m >= 1; a(2*m + 1) = 6*m + 1, m >= 0. - Ralf Steiner, May 17 2018
From Amiram Eldar, Nov 22 2024: (Start)
Product_{n>=1} (1 - (-1)^n/a(n)) = sqrt(3) (A002194).
Product_{n>=2} (1 + (-1)^n/a(n)) = Pi/3 (A019670). (End)

A005186 a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 10, 14, 18, 24, 29, 36, 44, 58, 72, 91, 113, 143, 179, 227, 287, 366, 460, 578, 732, 926, 1174, 1489, 1879, 2365, 2988, 3780, 4788, 6049, 7628, 9635, 12190, 15409, 19452, 24561, 31025, 39229, 49580, 62680, 79255, 100144

Offset: 0

N. J. A. Sloane, R. K. Guy

Appears to settle into approximately exponential growth after about 25 terms or so with a ratio between adjacent terms of roughly 1.264. - Howard A. Landman, May 24 2003
David W. Wilson (Jun 10 2003) gives a heuristic argument that the constant should be the largest eigenvalue of the matrix [ 1 0 0 1 0 0 / 0 0 0 0 1/3 0 / 0 1 0 0 1 0 / 0 0 0 0 1/3 0 / 0 0 1 0 0 1 / 0 0 0 0 1/3 0 ], which is (3 + sqrt(21))/6 = 1.2637626... = A176014.
Merlini and Sala (1999) deduce the value (1 + sqrt(7/3))/2 (A176014) for the asymptotic ratio a(n+1)/a(n) for n -> oo and call this "Collatz's constant". This is the same value as the constant mentioned above, see the "Heuristic argument for the asymptotic value (3 + sqrt(21))/6 of the ratio a(n+1)/a(n)" note in the Links section. - Markus Sigg, Nov 27 2020

R. K. Guy, personal communication.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.
Danilo Merlini and Nicoletta Sala, On the Fibonacci's Attractor and the Long Orbits in the 3n+1 Problem, International Journal of Chaos Theory and Applications, Vol. 4, No. 2-3 (1999), 75-84.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Markus Sigg, Table of n, a(n) for n = 0..125 (first 71 terms from T. D. Noe, terms up to n = 120 from Bert Dobbelaere).
S. N. Anderson, Struggling with the 3x+1 problem, Math. Gazette, 71 (1987), 271-274.
S. N. Anderson, Struggling with the 3x+1 problem, Math. Gazette, 71 (1987), 271-274. [Annotated scanned copy]
R. K. Guy, S. N. Anderson, and N. J. A. Sloane, Correspondence, 1988.
Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
Wolfdieter Lang, On Collatz Words, Sequences, and Trees, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
Hugo Pfoertner, Ratio of successive terms, illustration of deviation from (3+sqrt(21))/6.
Markus Sigg, Heuristic argument for the asymptotic value (3+sqrt(21))/6 of the ratio a(n+1)/a(n).
Wikipedia, The beginning of the Collatz directed graph
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A088975, A176014, A176866.

(* This program is not suitable to compute more than 20 terms *) maxiSteps = 20; mMaxi = 2*10^6; Clear[a]; a[] = 0; steps[m] := steps[m] = Module[{n = m, ns = 0}, While[n != 1, If[Mod[n, 2] == 0, n = n/2, n = 3*n+1]; ns++]; ns]; Do[sn = steps[m]; If[sn <= maxiSteps, a[sn] = a[sn]+1; Print["m = ", m, " a(", sn, ") = ", a[sn]]], {m, 1, mMaxi}]; Table[a[n], {n, 0, maxiSteps}] (* Jean-François Alcover, Oct 18 2013 *)
(* 60 terms in under a minute *) s = {1}; t = Join[{1}, Table[s = Union[2*s, (Select[s, Mod[#, 3] == 1 && OddQ[(# - 1)/3] && (# - 1)/3 > 1 &] - 1)/3]; Length[s], {n, 60}]] (* T. D. Noe, Oct 18 2013 *)

first(n)=my(v=vector(n+1), u=[1], old=u, w); v[1]=1; for(i=1, n, w=List(); for(j=1, #u, listput(w, 2*u[j]); if(u[j]%6==4, listput(w, u[j]\3))); old=setunion(old, u); u=setminus(Set(w), old); v[i+1]=#u); v \\ Charles R Greathouse IV, Jun 26 2017

first(n)={my(v=Vec([1, 1, 1, 1, 1], n+1), u=[16]); for(i=5, n, u=concat(2*u, [x\3 | x<-u, x%6==4 ]); v[i+1]=#u); v} \\ Joe Slater, Sep 01 2024

#!/usr/bin/perl @old = ( 1 ); while (1) { print scalar(@old), " "; @new = ( ); foreach $n (@old) { $used{$n} = 1; if (($n % 6) == 4) { $m = ($n-1)/3; push(@new,$m) unless ($used{$m}); } $m = $n + $n; push(@new,$m) unless ($used{$m}); } @old = @new; }

def search(x,d,lst):
    while d>0:
        lst[d]+=1
        if x%6==4 and x>4:
            search(x//3,d-1,lst)
        x*=2
        d-=1
    lst[d]+=1
def A005186_list(n_max):
    lst=[0]*(n_max+1)
    search(1,n_max,lst)
    return lst[::-1]
# Bert Dobbelaere, Sep 09 2018

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

A263267 Breadth-first traversal of the tree defined by the edge-relation A049820(child) = parent.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 8, 9, 10, 12, 7, 11, 14, 18, 13, 15, 16, 20, 22, 17, 24, 25, 26, 28, 30, 19, 21, 32, 34, 23, 40, 38, 42, 27, 44, 48, 46, 29, 36, 50, 56, 60, 49, 52, 54, 31, 33, 72, 58, 35, 84, 62, 66, 37, 39, 96, 68, 70, 41, 45, 104, 108, 74, 76, 78, 80, 43, 47, 120, 81, 82, 90, 88, 51, 128, 132, 83, 85, 86, 94, 53, 55, 136, 140, 87, 92, 102

Offset: 0

Antti Karttunen, Nov 27 2015

It is conjectured that the terms of A259934 trace the only infinite path in this tree.

After the root (0), the tree narrows next time to the width of just one node at level A262508(1) = 9236, with vertex 119143.

			Rows 0 - 21 of the table. The lines show the nodes of the tree connected by the edge-relation A049820(child) = parent:
0;
| \
1, 2;
| \  \
3, 4, 6;____
|  |  | \   \
5, 8, 9, 10, 12;
|     |   |   |
7, _ 11, 14, 18;
  /  | \   \   \
13, 15, 16, 20, 22;____
     |  |      / | \   \
    17, 24, 25, 26, 28, 30;
     | \         |      |
    19, 21,     32,     34;
         |       |      | \
        23,     40,    38, 42;____
         |              | \       \
        27,            44, 48,     46;____
         | \            |   | \    |  \   \
        29, 36,        50, 56, 60, 49, 52, 54;
         | \                   |           |
        31, 33,                72,         58;
         |                     |           |  \
        35,                    84,         62, 66;
         | \                   |           |  \
        37, 39,                96,         68, 70;_______
            |  \               |  \           / |  \     \
            41, 45,           104, 108,     74, 76, 78,   80;
            |   |              |                |   |  \    \
            43, 47,           120,             _81, 82, 90, 88;
                |              |  \           / |   |   |
                51,           128, 132,     83, 85, 86, 94;
                 | \            | \          |       |   |
                53, 55        136, 140      87,     92, 102;______
                 |                           | \     |    |  \    \
                57,_                        89, 91, 98, 106,  110, 112;
               / |  \                       /   / \       |     |
             59, 63, 64,                  93, 95, 100,   114,   116;
              |                            |   |          |  \
             61,                          99, 97,       _118, 126;
              |                            |   |       /  |  \
             65,                         101, 105,  121, 122, 124;
(See also _Michael De Vlieger_'s poster in the Links section.)

Antti Karttunen, Table of n, a(n) for n = 0..10425; levels 0 .. 1001 of the tree
Michael De Vlieger, Poster illustrating A259934 and A263267
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A263268.
Cf. A000005, A049820, A060990, A082284, A155043, A259934, A262508.
Cf. A262507 (number of terms on row/level n), A263260 (total number of terms in levels 0 .. n).
Cf. A264988 (the left edge), this differs from A261089 (the least term on each level) for the first time at level 69.
Cf. A263269 (the right edge).
Cf. A262686 (maximum term on the level n).
Cf. A045765 (the leaves of the tree).
Cf. also permutations A263265 (obtained from this table by sorting each row into ascending order), A263266.
Cf. also arrays A265751 and A263271.
Differs from A263265 for the first time at n=31, where a(31) = 40, while A263265(31) = 38.
Cf. also A088975.

uplim = 125753; \\ = A263260(10001).
checklimit = 1440; \\ Hard limit 1440 good for at least up to A002182(67) = 1102701600 as A002183(67) = 1440.
v263267 = vector(uplim);
A263267 = n -> if(!n,n,v263267[n]);
z = 0; for(n=0, uplim, t = A263267(n); write("b263267.txt", n, " ", t); for(k=t+1, t+checklimit, if((k-numdiv(k)) == t, z++; if(z <= uplim, v263267[z] = k))));

# After David Eppstein's Python-code for A088975.
def A263267():
  '''Breadth-first reading of irregular tree defined by the edge-relation A049820(child) = parent'''
  yield 0
  for x in A263267():
    for k in [x+1 .. 2*(x+1)]:
      if ((k - sloane.A000005(k)) == x): yield k
def take(n,g):
  '''Returns a list composed of the next n elements returned by generator g.'''
  return [next(g) for _ in range(n)]
take(120, A263267())

;; This version creates the list of terms incrementally, using append! function that physically modifies the list at the same time as it is traversed. Otherwise the idea is essentially the same as with Python/Sage-program above:
(define (A263267list_up_to_n_terms_at_least n) (let ((terms-produced (list 0))) (let loop ((startp terms-produced) (endp terms-produced) (k (- n 1))) (cond ((<= k 0) terms-produced) (else (let ((children (children-of-n-in-A049820-tree (car startp)))) (cond ((null? children) (loop (cdr startp) endp k)) (else (begin (append! endp children) (loop (cdr startp) children (- k (length children))))))))))))
(define (children-of-n-in-A049820-tree n) (let loop ((k (A262686 n)) (children (list))) (cond ((<= k n) children) ((= (A049820 k) n) (loop (- k 1) (cons k children))) (else (loop (- k 1) children)))))

A127824 Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.

Original entry on oeis.org

1, 2, 4, 8, 16, 5, 32, 10, 64, 3, 20, 21, 128, 6, 40, 42, 256, 12, 13, 80, 84, 85, 512, 24, 26, 160, 168, 170, 1024, 48, 52, 53, 320, 336, 340, 341, 2048, 17, 96, 104, 106, 113, 640, 672, 680, 682, 4096, 34, 35, 192, 208, 212, 213, 226, 227, 1280, 1344, 1360, 1364

Offset: 0

T. D. Noe, Jan 31 2007

The length of each row is A005186(n). The largest number in row n is 2^n. The second-largest number in row n is A000975(n-2) for n>4. The smallest number in row n is A033491(n). The Collatz conjecture asserts that every positive integer occurs in some row of this triangle.
n is an element of row number A006577(n). - Reinhard Zumkeller, Oct 03 2012
Conjecture: The numbers T(n, 1),...,T(n, k_n) of row n are arranged in non-overlapping clusters of numbers which have the same order of magnitude and whose Collatz trajectories to 1 have the same numbers of ups and downs. The highest cluster of row n is just the number 2^n, the trajectory to 1 of which has n-1 downs and no ups. The second highest cluster of row n consists of the numbers T(n, k_n - r) = 4^(r - 1) * t(n - 2*r + 2) for 1 <= r <= (n - 3) / 2, where t(k) = (2^k - (-1)^k - 3) / 6. These have n-2 downs and one up. The largest and second largest number of this latter cluster are given by A000975 and A153772. - Markus Sigg, Sep 25 2020

			The triangle starts:
   0:   1
   1:   2
   2:   4
   3:   8
   4:  16
   5:   5   32
   6:  10   64
   7:   3   20   21  128
   8:   6   40   42  256
   9:  12   13   80   84   85  512
  10:  24   26  160  168  170 1024
  11:  48   52   53  320  336  340  341 2048
  12:  17   96  104  106  113  640  672  680  682 4096
- _Reinhard Zumkeller_, Oct 03 2012

See also A006577.

Alois P. Heinz, Rows n = 0..42, flattened (first 31 rows from T. D. Noe)
Paul Andaloro, On total stopping times under 3x+1 iteration, Fib. Quar. 38 (1) (2000) 73.
Jason Davies, Collatz Graph: All Numbers Lead to One
Wolfdieter Lang, On Collatz Words, Sequences, and Trees, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
Markus Sigg, On the cluster structures in Collatz preimages, arXiv:2012.07839 [math.GM], 2020.
Wikipedia, Collatz Conjecture

Cf. A006577 (total stopping time of n), A088975 (traversal of the Collatz tree).
Column k=1 gives A033491.
Last elements of rows give A000079.
Row lengths give A005186.
Row sums give A337673(n+1).

import Data.List (union, sort)
a127824 n k = a127824_tabf !! n !! k
a127824_row n = a127824_tabf !! n
a127824_tabf = iterate f [1] where
   f row = sort $ map (* 2) row `union`
                  [x' | x <- row, let x' = (x - 1) `div` 3,
                        x' * 3 == x - 1, odd x', x' > 1]
-- Reinhard Zumkeller, Oct 03 2012

s={1}; t=Flatten[Join[s, Table[s=Union[2s, (Select[s,Mod[ #,3]==1 && OddQ[(#-1)/3] && (#-1)/3>1&]-1)/3]; s, {n,13}]]]

Suppose S is the list of numbers in row n. Then the list of numbers in row n+1 is the union of each number in S multiplied by 2 and the numbers (x-1)/3, where x is in S, with x=1 (mod 3) and where (x-1)/3 is an odd number greater than 1.

A248573 An irregular triangle giving the Collatz-Terras tree.

Original entry on oeis.org

1, 2, 4, 8, 5, 16, 3, 10, 32, 6, 20, 21, 64, 12, 13, 40, 42, 128, 24, 26, 80, 84, 85, 256, 48, 17, 52, 53, 160, 168, 170, 512, 96, 11, 34, 104, 35, 106, 320, 336, 113, 340, 341, 1024, 192, 7, 22, 68, 69, 208, 23, 70, 212, 213, 640, 672, 75, 226, 680, 227, 682, 2048

Offset: 0

Nico Brown, Oct 08 2014

From Wolfdieter Lang, Oct 31 2014: (Start)
(old name corrected)
Irregular triangle CT(l, m) such that the first three rows l = 0, 1 and 2 are 1, 2, 4, respectively, and for l >= 3 the row entries CT(l, m) are obtained from replacing the numbers of row l-1 by (2*x-1)/3, 2*x if they are 2 (mod 3) and by 2*x otherwise.
The modified Collatz (or Collatz-Terras) map sends a positive number x to x/2 if it is even and to (3*x+1)/2 if it is odd (see A060322). The present tree (without the complete tree originating at CT(2,1) = 1) can be considered as an incomplete binary tree, with nodes (vertices) of out-degree 2 if they are 2 (mod 3) and out-degree 1 otherwise. In the example below, the edges (branches) could be labeled L (left) or V (vertical).
The row length sequence is A060322(l+1), l>=0. (End)
The Collatz conjecture is true if and only if all odd numbers appear in this sequence.
This sequence is similar to A127824.

			The irregular triangle CT(l,m) begins:
l\m   1   2  3   4   5   6   7   8   9  10  11   12  13   14   15  16  17   18   19  20  21   22   23   24 ...
0:    1
1:    2
2:    4  here the 1, which would generate the complete tree again, is omitted
3:    8
4:    5  16
5:    3  10 32
6:    6  20 21  64
7:   12  13 40  42 128
8:   24  26 80  84  85 256
9:   48  17 52  53 160 168 170 512
10:  96  11 34 104  35 106 320 336 113 340 341 1024
11: 192   7 22  68  69 208  23  70 212 213 640  672  75  226  680 227 682 2048
12: 384  14 44  45 136 138 416  15  46 140 141  424 426 1280 1344 150 452  453 1360 151 454 1364 1365 4096
... reformatted, and extended - _Wolfdieter Lang_, Oct 31 2014
--------------------------------------------------------------------------------------------------------------
From _Wolfdieter Lang_, Oct 31 2014: (Start)
The Collatz-Terras tree starting with 4 looks like (numbers x == 2 (mod 3) are marked with a left bar, and the left branch ends then in (2*x-1)/3 and the vertical one in 2*x)
l=2:                                                                                        4
l=3:                                                                                       |8
l=4:                                                    |5                                 16
l=5:    3                                               10                                |32
l=6:    6                                              |20   21                            64
l=7:   12                     13                        40   42                          |128
l=8:   24                    |26                       |80   84            85             256
l=9:   48           |17       52              |53      160  168          |170            |512
l=10:  96     |11    34     |104        |35   106      320  336     |113  340      |341  1024
l=11: 192   7  22   |68  69  208   23|   70   212  213 640  672  75  226  680  227  682  2048
...
E.g., x = 7 = CT(11, 2) leads back to 4 via 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, and from there back to 2, 1.
(End)
--------------------------------------------------------------------------------------------------------------

Sebastian Karlsson, Rows l = 0..35, flattened
Riho Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976) 241-252.
Eric Weisstein's World of Mathematics, Collatz Problem.

Cf. A127824, A060322, A088975.

Join[{{1}, {2}}, NestList[Flatten[Map[If[Mod[#, 3] == 2, {(2*#-1)/3, 2*#}, 2*#]&, #]]&, {4}, 10]] (* Paolo Xausa, Jan 25 2024 *)

rows(N) = my(r=List(),x); for(i=0, min(2, N), listput(r, x=[2^i])); for(n=3, N, my(w=List()); for(i=1, #x, my(q=2*x[i]); if(1==q%3, listput(w, (q-1)/3)); listput(w, q)); listput(r, x=Vec(w))); Vec(r); \\ Ruud H.G. van Tol, Jan 25 2024

Edited. New name (old corrected name as comment). - Wolfdieter Lang, Oct 31 2014

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)

A261702 a(1) = 1; for n>1, a(n) is the smallest positive integer not already present which is entailed by the rules (i) k present => 2k present; (ii) 3k+1 present and k odd => k present.

Original entry on oeis.org

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 20, 24, 32, 40, 13, 26, 48, 52, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 44, 56, 64, 21, 42, 68, 72, 80, 84, 88, 29, 58, 19, 38, 76, 25, 50, 96, 100, 33, 66, 104, 112, 37, 74, 116, 128, 132, 136, 45, 90, 144, 148, 49, 98, 152

Offset: 1

Paul Tek, Aug 28 2015

If the Collatz 3n+1 conjecture is true, then this is a permutation of all positive integers. See A261715 for putative inverse.

Paul Tek, Table of n, a(n) for n = 1..10000
Paul Tek, PERL program for this sequence
Paul Tek, C++ program for this sequence
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A088975, A033491, A109732, A261690, A261715 (putative inverse).

a:= proc() local a, b, s; b, s:= proc() true end,
      heap[new]((x, y)-> is(x>y), 1); a:=
      proc(n) option remember; local k, t;
        if n>1 then a(n-1) fi;
        t:= heap[extract](s); b(t):= false;
        k:= 2*t; if b(k) then heap[insert](k, s) fi;
        if irem(t-1, 3, 'k')=0 and (k::odd) and
          b(k) then heap[insert](k, s) fi; t
      end
    end():
seq(a(n), n=1..80);  # Alois P. Heinz, Aug 29 2015

See Links section.
(C++) See Links section.

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

A324035 Irregular triangle read by rows of the entries of the Collatz tree A088975 modulo 6, starting with entry 8 == 2 (mod 6).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A343280 a(n) is the number of steps for the n-th vertex of the Collatz tree A088975 to reach a vertex t == 0 (mod 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

BASIC

Formula

A007310 Numbers congruent to 1 or 5 mod 6.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Sage

Formula

A005186 a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Perl

Python

Extensions

A263267 Breadth-first traversal of the tree defined by the edge-relation A049820(child) = parent.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

Scheme

A127824 Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula