A176866 -id:A176866 - cp's OEIS frontend

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

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

A088975 Breadth-first traversal of the Collatz tree, with the odd child of each node traversed prior to its even child. If the Collatz 3n+1 conjecture is true, this is a permutation of all positive integers.

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, 96, 17, 104, 106, 640, 672, 113, 680, 682, 4096, 192, 34, 208, 35, 212, 213, 1280, 1344, 226, 1360, 227, 1364

Offset: 0

David Eppstein, Oct 31 2003

From Wolfdieter Lang, Nov 26 2013: (Start)
The length of row (level) l of this table is A005186(l).
The (incomplete) ternary subtree starting with the vertex labeled 8 at level l=3 obeys the rules: (i) The three possible edge (branch) labels are L, V, R (for left, vertical and right). (ii) If the vertex label m is congruent to 4 modulo 6 then the out-degree is 2 and the edge labeled L ends in a vertex with label (m-1)/3 and the edge labeled R ends in a vertex with label 2*m. Otherwise (if the vertex label m is congruent to 0, 1, 2, 3, 5 (mod 6)) the out-degree is 1 with the edge labeled V ending in a vertex with label 2*m. See the Python program.
On top of this tree starting with node label 8 one puts the unary tree (out-degree 1) with vertex labels 1, 2, and 4, where each edge label is V. The 1, at level l=0, labels the root of the Collatz tree CT. Note that 4 at level l=2 has out-degree 1 and not 2 even though 4 == 4 (mod 6). This exception is needed because otherwise the L branch would result in a repetition of the whole CT tree.
Alternatively one could start a Collatz tree with vertex label 4 at level 0, using the above given rules, but cut off the L branch originating from 4 after level 2 (out-degree of vertex labeled 2 is 0). Without this cut 4 would appear again and the whole tree would be repeated.
The number of vertex labels with CT(l,k) == 4 (mod 6) with l >= 3 is A176866(l+1).
From level l=16 on the left-right symmetry in the branch structure (forgetting about the vertex labels) of the subtree starting with label 16 at level l=4 is no longer present because the row length A005186(16) = 29, which is odd. (End)

			From _Wolfdieter Lang_, Nov 26 2013: (Start)
At the start of table CT the 4 (mod 6) vertex labels CT(l,k) with l >= 4 and out-edges L and R have been put into brackets. The other labels have out-degree 1 with edge label V). A bar separates the left and right subtree originating at vertex 16.
l\k  1    2    3      4     5     6     7    8    9     10 ...
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: 96   17  104   (106) (640) | 672  113  680 (682) (4096)
...
l=13: 192 (34) (208) 35 212 213 1280 | 1344 (226) (1360) 227 1364 1365 8192.
l=14: 384 11 68 69 416 (70) (424) 426 (2560) | 2688 75 452 453  2720 (454) (2728) 2730 (16384).
l=15: 768 (22) (136) 138 (832) 23 140 141 848 852 853 5120 |  5376 150 (904) 906 (5440) 151 908 909 5456 5460 5461 32768.
At level l=15 the left-right 4 (mod 6) structure becomes for the first time asymmetric. This leads at the next level l=16 to the number of vertices  12+3 | 12+2 = 15|14 in total 29 (odd), breaking the left-right branch symmetry.
The alternative Collatz tree, mentioned in a comment above, starts (here the vertex labeled 2 has now out-degree 0):
l\k  1     2     3      4     5      6     7     8  ...
0:  (4)
1:   1     8
2:   2   (16)
3:   5    32
4:  (10) (64)
5:   3    20    21    128
6:   6   (40)   42   (256)
7:  12    13    80     84    85    512
8:  24    26  (160)   168   170  (1024)
9:  48   (52)   53    320   336   (340)  341  2048
... (End)

T. D. Noe, Table of n, a(n) for n = 0..3517

Cf. A127824 (terms at the same depth are sorted). A005186 (row length), A176866 (number of 4 (mod 6) labels, l >= 3).

def A088975():
    yield 1
    for x in A088975():
        if x > 4 and x % 6 == 4:
            yield (x-1)/3
        yield 2*x

Keyword tabf, notation CT(l,k) and two crossrefs added by Wolfdieter Lang, Nov 26 2013

A090458 Decimal expansion of (3 + sqrt(21))/2.

Original entry on oeis.org

3, 7, 9, 1, 2, 8, 7, 8, 4, 7, 4, 7, 7, 9, 2, 0, 0, 0, 3, 2, 9, 4, 0, 2, 3, 5, 9, 6, 8, 6, 4, 0, 0, 4, 2, 4, 4, 4, 9, 2, 2, 2, 8, 2, 8, 8, 3, 8, 3, 9, 8, 5, 9, 5, 1, 3, 0, 3, 6, 2, 1, 0, 6, 1, 9, 5, 3, 4, 3, 4, 2, 1, 2, 7, 7, 3, 8, 8, 5, 4, 4, 3, 3, 0, 2, 1, 8, 0, 7, 7, 9, 7, 4, 6, 7, 2, 2, 5, 1, 6, 3

Offset: 1

Felix Tubiana, Feb 05 2004

Decimal expansion of the solution to n/x = x-n for n-3. n/x = x-n with n=1 gives the Golden Ratio = 1.6180339887...
n/x = x-n ==> x^2 - n*x - n = 0 ==> x = (n + sqrt(n^2 + 4*n)) / 2 (Positive Root) n = 3: x = (3 + sqrt(21))/2 = 3.79128784747792...
x=3.7912878474... is the shape of a rectangle whose geometric partition (as at A188635) consists of 3 squares, then 1 square, then 3 squares, etc., matching the continued fraction of x, which is [3,1,3,1,3,1,3,1,3,1,...]. (See the Mathematica program below.) - Clark Kimberling, May 05 2011
x appears to be the limit for n to infinity of the ratio of the number of even numbers that take n steps to reach 1 to the number of odd numbers that take n steps to reach 1 in the Collatz iteration. As A005186(n-1) is the number of even numbers that take n steps to reach 1, this means x = lim A005186(n-1)/A176866(n). - Markus Sigg, Oct 20 2020
From Wolfdieter Lang, Sep 02 2022: (Start)
This integer in the quadratic number field Q(sqrt(21)) equals the (real) cube root of 27 + 6*sqrt(21) = 54.4954541... . See Euler, Elements of Algebra, Article 748 or Algebra (in German) p. 306, Kapitel 12, 187.
Subtracting 3 from the present number gives the (real) cube root of
  -27 +  6*sqrt(21) = 0.4954541... . (End)

			3.79128784747792...

Leonhard Euler, Vollständige Anleitung zur Algebra, (1770), Reclam, Leipzig, 1883, p.306, Kapitel 12, 187.

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Leonhard Euler, Elements of Algebra, p. 244, Article 748.
Markus Sigg, Heuristic argument for the asymptotic value of the even/odd ratio of number of steps in the Collatz iteration, 2020.
Index entries for algebraic numbers, degree 2

Of the same type as this: A090388 (n=2), A090488 (n=4), A090550 (n=5), A092294 (n=6), A092290 (n=7), A090654 (n=8), A090655 (n=9), A090656 (n=10).
Equals 3*A176014 (constant).
Cf. A356034.

FromContinuedFraction[{3,1,{3,1}}]
ContinuedFraction[%,20]
RealDigits[N[%%,120]] (*A090458*)
N[%%%,40]
RealDigits[(3 + Sqrt[21])/2, 10, 50][[1]] (* G. C. Greubel, Jul 03 2017 *)

solve(x=3,4,x^2-3*x-3) \\ Charles R Greathouse IV, Oct 04 2011

(3+sqrt(21))/2 \\ Charles R Greathouse IV, Oct 04 2011

Equals (27 + 6*sqrt(21))^(1/3). - Wolfdieter Lang, Sep 01 2022

Additional comments from Rick L. Shepherd, Jul 02 2004

A176014 Decimal expansion of (3+sqrt(21))/6.

Original entry on oeis.org

1, 2, 6, 3, 7, 6, 2, 6, 1, 5, 8, 2, 5, 9, 7, 3, 3, 3, 4, 4, 3, 1, 3, 4, 1, 1, 9, 8, 9, 5, 4, 6, 6, 8, 0, 8, 1, 4, 9, 7, 4, 0, 9, 4, 2, 9, 4, 6, 1, 3, 2, 8, 6, 5, 0, 4, 3, 4, 5, 4, 0, 3, 5, 3, 9, 8, 4, 4, 7, 8, 0, 7, 0, 9, 2, 4, 6, 2, 8, 4, 8, 1, 1, 0, 0, 7, 2, 6, 9, 2, 6, 5, 8, 2, 2, 4, 0, 8, 3, 8, 7, 7, 9, 6, 0

Offset: 1

Klaus Brockhaus, Apr 06 2010

Continued fraction expansion of (3+sqrt(21))/6 is A010684.

Also greatest eigenvalue of the 6 X 6 matrix [[3 0 0 3 0 0][0 0 0 0 1 0][0 3 0 0 3 0][0 0 0 0 1 0][0 0 3 0 0 3][0 0 0 0 1 0]]/3. It is conjectured that this is lim_{k->infinity} A005186(k+1)/A005186(k), i.e., the asymptotic growth rate of the number of numbers with the same total stopping time in the Collatz iteration. - Hugo Pfoertner, Sep 28 2020

			(3+sqrt(21))/6 = 1.26376261582597333443...

Daniel Starodubtsev, Table of n, a(n) for n = 1..10000
Hugo Pfoertner, Ratio of successive terms in A005186, illustration of deviation from (3+sqrt(21))/6.
Index entries for algebraic numbers, degree 2.

Cf. A010477 (decimal expansion of sqrt(21)).
Cf. A010684 (repeat 1, 3), A136210, A136211.
Cf. A005186, A006577, A127824, A176866.

RealDigits[(3+Sqrt[21])/6,10,120][[1]] (* Harvey P. Dale, Jul 21 2023 *)

vecmax(mateigen([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],1)[1]) \\ Hugo Pfoertner, Sep 28 2020

A176867 Least odd number that requires n Collatz (3x+1) iterations to reach 1, or zero if there is no such number.

Original entry on oeis.org

1, 0, 0, 0, 0, 5, 0, 3, 0, 13, 0, 53, 17, 35, 11, 23, 7, 15, 29, 9, 19, 37, 77, 25, 49, 99, 33, 65, 131, 43, 87, 173, 57, 115, 39, 79, 153, 305, 105, 203, 407, 135, 271, 541, 185, 361, 123, 247, 481, 169, 329, 641, 219, 427, 159, 295, 569, 1139, 379, 759, 283, 505, 1011

Offset: 0

T. D. Noe, Apr 27 2010

nonn

Both the 3x+1 steps and the halving steps are counted. a(n)=0 only for n = 1, 2, 3, 4, 6, 8, and 10. Sequence A033491 gives the least even or odd number requiring n iterations.

T. D. Noe, Table of n, a(n) for n=0..1924

Cf. A176866, A176868

A176868 Greatest odd number that requires n Collatz (3x+1) iterations to reach 1, or zero if there is no such number.

Original entry on oeis.org

1, 0, 0, 0, 0, 5, 0, 21, 0, 85, 0, 341, 113, 1365, 453, 5461, 1813, 21845, 7281, 87381, 29125, 349525, 116501, 1398101, 466033, 5592405, 1864133, 22369621, 7456533, 89478485, 29826161, 357913941, 119304645, 1431655765, 477218581, 5726623061, 1908874353

Offset: 0

T. D. Noe, Apr 27 2010

nonn

Both the 3x+1 steps and the halving steps are counted. a(n)=0 only for n = 1, 2, 3, 4, 6, 8, and 10.

T. D. Noe, Table of n, a(n) for n = 0..400

Cf. A176866, A176867.

nn = 10; t1 = {0, 0, 5, 21, 85, 341, 1365}; Do[AppendTo[t1, 4 t1[[-1]] + 1], {3*nn}]; t2 = {1, 0, 0, 0, 0, 0, 113}; Do[AppendTo[t2, 4 t2[[-1]] + 1]; AppendTo[t2, 4 t2[[-1]] + 1]; AppendTo[t2, 4 t2[[-1]] + 29], {nn}]; t = Riffle[t2, t1] (* T. D. Noe, Feb 14 2013 *)

A221473 Irregular table of odd numbers whose n-th row has numbers taking n iterations of the Collatz (3x+1) function to reach 1.

Original entry on oeis.org

1, 5, 3, 21, 13, 85, 53, 341, 17, 113, 35, 213, 227, 1365, 11, 69, 75, 453, 23, 141, 151, 853, 909, 5461, 7, 45, 277, 301, 1813, 15, 93, 565, 605, 3413, 3637, 21845, 29, 181, 201, 1109, 1137, 1205, 7253, 7281, 9, 61, 369, 373, 401, 403, 2261, 2275, 2417

Offset: 0

T. D. Noe, Feb 13 2013

Sequence A176866 gives the length of each row. Sequences A176867 and A176868 give the minimum and maximum number in each row. Observe how each row has clumps of numbers -- a feature evident in the graph. Sequence A221474 counts these clumps.

			Rows 0 to 18 are
{1}
{}
{}
{}
{}
{5}
{}
{3, 21}
{}
{13, 85}
{}
{53, 341}
{17, 113}
{35, 213, 227, 1365}
{11, 69, 75, 453}
{23, 141, 151, 853, 909, 5461}
{7, 45, 277, 301, 1813}
{15, 93, 565, 605, 3413, 3637, 21845}
{29, 181, 201, 1109, 1137, 1205, 7253, 7281}
...
Note that row 18 has 4 clumps: 29, 181-201, 1109-1205, and 7253-7281.

T. D. Noe, Rows n = 0..40 of triangle, flattened

Cf. A176866, A176867, A176868.
Cf. A127824 (table of even and odd numbers taking n iterations).
Cf. A221474 (number of clumps).

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

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

Original entry on oeis.org

2, 4, 5, 2, 4, 4, 3, 2, 3, 2, 0, 4, 0, 4, 0, 1, 2, 0, 1, 2, 0, 2, 4, 0, 2, 4, 0, 4, 5, 2, 0, 4, 5, 2, 0, 5, 2, 4, 4, 0, 5, 2, 4, 4, 0, 4, 4, 5, 2, 3, 2, 0, 4, 4, 5, 2, 3, 2, 0, 5, 2, 3, 2, 4, 4, 0, 4, 0, 3, 2, 3, 2, 4, 4, 0, 4

Offset: 0

Wolfdieter Lang, Feb 14 2019

The length of row l of this irregular triangle is A005186(n+3), n >= 0.
The entries of the Collatz tree A088975 modulo 6 are interesting because each 4 (mod 6) entry belongs to a vertex with outdegree 2 and all other vertices have outdegree 1. See a comment in A088975. The root 8 is chosen because the vertex 4 of the preceding level does not obey this rule  (otherwise a tree repetiton would occur).
The number of entries of level n congruent to 4 modulo 6 are given by A176866(n+4), for n >= 0.

			The irregular triangle T begins:
n\k   1 2 3 4 5 6 7 8 9 10 11 12 13 14  15 16 17 18 ...   A005186(n+3)
0:    2                                                         1
1:    4                                                         1
2:    5 2                                                       2
3:    4 4                                                       2
4:    3 2 3 2                                                   4
5:    0 4 0 4                                                   4
6:    0 1 2 0 1 2                                               6
7:    0 2 4 0 2 4                                               6
8:    0 4 5 2 0 4 5 2                                           8
9:    0 5 2 4 4 0 5 2 4  4                                     10
10:   0 4 4 5 2 3 2 0 4  4  5  2  3  2                         14
11:   0 5 2 3 2 4 4 0 4  0  3  2  3  2  4  4   0   4           18
...

Cf. A005186, A088975, A176866.

T(n, k) = A088975(n+3, k) (mod 6), k = 1..A005186(n+3), n >= 0.

cp's OEIS Frontend

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

A088975 Breadth-first traversal of the Collatz tree, with the odd child of each node traversed prior to its even child. If the Collatz 3n+1 conjecture is true, this is a permutation of all positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A090458 Decimal expansion of (3 + sqrt(21))/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A176014 Decimal expansion of (3+sqrt(21))/6.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A176867 Least odd number that requires n Collatz (3x+1) iterations to reach 1, or zero if there is no such number.

Views

Author

Keywords

Comments

Links

Crossrefs

A176868 Greatest odd number that requires n Collatz (3x+1) iterations to reach 1, or zero if there is no such number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A221473 Irregular table of odd numbers whose n-th row has numbers taking n iterations of the Collatz (3x+1) function to reach 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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