A075483 -id:A075483 - cp's OEIS frontend

A074473 Dropping time for the 3x+1 problem: for n >= 2, number of iteration that first becomes smaller than the initial value if Collatz-function (A006370) is iterated starting at n; a(1)=1 by convention.

1, 2, 7, 2, 4, 2, 12, 2, 4, 2, 9, 2, 4, 2, 12, 2, 4, 2, 7, 2, 4, 2, 9, 2, 4, 2, 97, 2, 4, 2, 92, 2, 4, 2, 7, 2, 4, 2, 14, 2, 4, 2, 9, 2, 4, 2, 89, 2, 4, 2, 7, 2, 4, 2, 9, 2, 4, 2, 12, 2, 4, 2, 89, 2, 4, 2, 7, 2, 4, 2, 84, 2, 4, 2, 9, 2, 4, 2, 14, 2, 4, 2, 7, 2, 4, 2, 9, 2, 4, 2, 74, 2, 4, 2, 14, 2, 4, 2, 7

Offset: 1

Labos Elemer, Sep 19 2002

nonn

Here we call the starting value iteration number 1, although usually the count is started at 0, which would subtract 1 from the values for n >= 2 - see A060445, A102419.

			n=2k: then a(2k)=2 because the second iterate is k<n=2k, the first iterate below 2k; n=4k+1, k>1: the list = {4k+1, 12k+4, 6k+2, 3k+1, ...} i.e. the 4th term is always the first below initial value, so a(4k+1)=4;
n=15: the list={15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1} and 12th term is first sinks below iv=15, so a(15)=12; relatively larger values occur at n=4k+3.
n=3: the list is {3, 10, 5, 16, 8, 4, 2, 1, ..}, the 7th term is 2, which is the first smaller than 3, so a(3)=7.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Cf. A006370, A075476, A075477, A075478, A075479, A075480, A075481, A075482, A075483, A060445, A060412, A217934.

Equals A102419(n)+1.

nextx[x_Integer] := If[OddQ@x, 3x + 1, x/2]; f[1] = 1; f[n_] := Length@ NestWhileList[nextx, n, # >= n &]; Array[f, 83] (* Bobby R. Treat (drbob(at)bigfoot.com), Sep 16 2006 *)

A074473(n) = if (n<3, n,  my(N=n, x=1); while (1, if (n%2==0, n/=2, n = 3*n + 1); x++; if (nMichel Marcus, Aug 15 2025

def a(n):
    if n<3: return n
    N=n
    x=1
    while True:
        if n%2==0: n/=2
        else: n = 3*n + 1
        x+=1
        if nIndranil Ghosh, Apr 15 2017

Edited by N. J. A. Sloane, Sep 15 2006

A076227 Number of surviving Collatz residues mod 2^n.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 8, 13, 19, 38, 64, 128, 226, 367, 734, 1295, 2114, 4228, 7495, 14990, 27328, 46611, 93222, 168807, 286581, 573162, 1037374, 1762293, 3524586, 6385637, 12771274, 23642078, 41347483, 82694966, 151917636, 263841377, 527682754, 967378591, 1934757182, 3611535862

Offset: 0

Labos Elemer, Oct 01 2002

nonn

Number of residue classes in which A074473(m) is not constant.
The ratio of numbers of inhomogenous r-classes versus uniform-classes enumerated here increases with n and tends to 0. For n large enough ratio < a(16)/65536 = 2114/65536 ~ 3.23%.
Theorem: a(n) can be generated for each n > 2 algorithmically in a Pascal's triangle-like manner from the two starting values 0 and 1. This result is based on the fact that the Collatz residues (mod 2^k) can be evolved according to a binary tree. There is a direct connectedness to A100982, A056576, A022921, A020915. - Mike Winkler, Sep 12 2017
Brown's criterion ensures that the sequence is complete (see formulae). - Vladimir M. Zarubin, Aug 11 2019

			n=6: Modulo 64, eight residue classes were counted: r=7, 15, 27, 31, 39, 47, 59, 63. See A075476-A075483. For other 64-8=56 r-classes u(q)=A074473(64k+q) is constant: in 32 class u(q)=2, in 16 classes u(q)=4, in 4 classes u(q)=7 and in 4 cases u(q)=9. E.g., for r=11, 23, 43, 55 A074473(64k+r)=9 independently of k.
From _Mike Winkler_, Sep 12 2017: (Start)
The next table shows how the theorem works. No entry is equal to zero.
  k =        3  4  5   6   7   8   9  10  11   12 .. | a(n)=
-----------------------------------------------------|
  n =  2  |  1                                       |    1
  n =  3  |  1  1                                    |    2
  n =  4  |     2  1                                 |    3
  n =  5  |        3   1                             |    4
  n =  6  |        3   4   1                         |    8
  n =  7  |            7   5   1                     |   13
  n =  8  |               12   6   1                 |   19
  n =  9  |               12  18   7   1             |   38
  n = 10  |                   30  25   8   1         |   64
  n = 11  |                   30  55  33   9    1    |  128
  :       |                        :   :   :    : .. |   :
-----------------------------------------------------|------
A100982(k) = 2  3  7  12  30  85 173 476 961 2652 .. |
The entries (n,k) in this table are generated by the rule (n+1,k) = (n,k) + (n,k-1). The last value of (n+1,k) is given by n+1 = A056576(k-1), or the highest value in column n is given twice only if A022921(k-2) = 2. Then a(n) is equal to the sum of the entries in row n. For k = 7 there is: 1 = 0 + 1, 5 = 1 + 4, 12 = 5 + 7, 12 = 12 + 0. It is a(9) = 12 + 18 + 7 + 1 = 38. The sum of column k is equal to A100982(k). (End)

Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Andreas-Stephan Elsenhans, Numerical verification of the Collatz conjecture for billion digit random numbers, arXiv:2502.16743 [math.NT], 2025.
Tomás Oliveira e Silva, Computational verification of the 3x+1 conjecture.
Eric Weisstein's World of Mathematics, Brown's Criterion
M. Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.

Cf. A006370, A074473, A075476-A075483, A100982, A056576, A022921, A020915, A243115.

/* call as follows: uint64_t s=survives(0,1,1,0,bits); */
uint64_t survives(uint64_t r, uint64_t m, uint64_t lm, int p2, int fp2)
{
    while(!(m&1) && (m>=lm)) {
        if(r&1) { r+=(r+1)>>1; m+=m>>1; }
        else { r>>=1; m>>=1; }
    }
    if(mPhil Carmody, Sep 08 2011 */

/* algorithm for the Theorem */
{limit=30; /*or limit>30*/ R=matrix(limit,limit); R[2,1]=0; R[2,2]=1; for(k=2, limit, if(k>2, print; print1("For n="k-1" in row n: ")); Kappa_k=floor(k*log(3)/log(2)); for(n=k, Kappa_k, R[n+1,k]=R[n,k]+R[n,k-1]); t=floor(1+(k-1)*log(2)/log(3)); a_n=0; for(i=t, k-1, print1(R[k,i]", "); a_n=a_n+R[k,i]); if(k>2, print; print(" and the sum is a(n)="a_n)))} \\ Mike Winkler, Sep 12 2017

a(n) = Sum_{k=A020915(n+2)..n+1} (n,k). (Theorem, cf. example) - Mike Winkler, Sep 12 2017
From Vladimir M. Zarubin, Aug 11 2019: (Start)
a(0) = 1, a(1) = 1, and for k > 0,
a(A020914(k)) = 2*a(A020914(k)-1) - A100982(k),
a(A054414(k)) = 2*a(A054414(k)-1). (End)
a(n) = 2^n - 2^n*Sum_{k=0..A156301(n)-1} A186009(k+1)/2^A020914(k). - Benjamin Lombardo, Sep 08 2019

New terms to n=39 by Phil Carmody, Sep 08 2011

A075482 Number of iteration that first becomes smaller than the initial value if Collatz-function (A006370) is iterated, starting with numbers of the form 64n + 59.

Original entry on oeis.org

12, 14, 12, 45, 12, 14, 12, 17, 12, 14, 12, 33, 12, 14, 12, 20, 12, 14, 12, 25, 12, 14, 12, 17, 12, 14, 12, 20, 12, 14, 12, 30, 12, 14, 12, 25, 12, 14, 12, 17, 12, 14, 12, 30, 12, 14, 12, 22, 12, 14, 12, 69, 12, 14, 12, 17, 12, 14, 12, 22, 12, 14, 12, 22, 12, 14, 12, 82, 12

Offset: 0

Labos Elemer, Sep 24 2002

nonn

1stSubmergeLengths[=A074473] with initial values belonging to other residue classes modulo 64 are either listed in A075476-A075483 or can be easily determined. For 64k+2s the first sink below initial value is at 2nd iterate; for 64k+4s+1 the first submerge below initial value comes at 4th term of iteration list; finally if initial value is of 64k+4s+3 form or moreover initial value = 64k+r, r = 3, 11, 19, 23, 35, 43, 51, 55, then for all k first sink emerges at the 7th, 9th, 7th, 9th, 7th, 9th, 7th, 9th iterates, respectively.

			n=0: 64n + 59 = 59, the list = {59,178,89,268,134,67,202,101,304,152,76,38,...} the 12th term = 38 < 59 = the initial value, so a(0)=12.

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370, A074472, A074473, A075476, A075477-A075483.

Table[Function[m, Length@ NestWhileList[If[EvenQ@ #, #/2, 3 # + 1] &, m, # >= m - 1 &]][64 n + 59], {n, 0, 84}] (* Michael De Vlieger, Mar 25 2017 *)

A006370(n) = if(n%2, 3*n+1, n/2);
A074473(n) = if(1==n,n,my(org_n=n); for(i=1,oo,if(nA006370(n)));
A075482(n) = A074473((64*n)+59); \\ Antti Karttunen, Oct 09 2018

a(n) = A074473(64n + 59).

A075480 Number of iteration that first becomes smaller than the initial value if Collatz function (A006370) is iterated, starting with numbers of the form 64n + 39.

Original entry on oeis.org

14, 69, 48, 20, 14, 27, 17, 33, 14, 20, 22, 40, 14, 58, 20, 17, 14, 33, 22, 33, 14, 64, 17, 33, 14, 71, 20, 35, 14, 40, 43, 17, 14, 71, 71, 25, 14, 27, 17, 40, 14, 22, 25, 27, 14, 43, 25, 17, 14, 66, 27, 25, 14, 76, 17, 20, 14, 22, 43, 27, 14, 66, 25, 17, 14, 22

Offset: 0

Labos Elemer, Sep 23 2002

Initial values of the form 64m + r, if r = {3,11,19,27,35,43,51,55}, provide first-sink-lengths {7,9,7,9,7,9,7,9} respectively; e.g., {64k + 19, 192k + 58, 96k + 29, 288k + 88, 144k + 44, 72k + 22, 36k + 11} submerge first below initial value at the 7th term, 36k + 11 < 64k + 19.

			n=0: 64n + 39 = 39, Collatz trajectory = {39, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, ....}, i.e., the 14th term = 38 is the first that is less than 39, the initial value, so a(0)=14.

Nathaniel Johnston, Table of n, a(n) for n = 0..10000

Cf. A074473, A074474, A075476-A075483, A006370.

col := proc(n) if(n mod 2 = 0)then return n/2: fi: return 3*n+1: end: A075480 := proc(n) local s,v: s:=1: v:=64*n+39: while v>=64*n+39 do v:=col(v): s:=s+1: od: return s: end: seq(A075480(n),n=0..65); # Nathaniel Johnston, Jun 22 2011

a(n) = A074473(64n+39).

Keyword:fini removed by Nathaniel Johnston, Jun 23 2011

Edited by Jon E. Schoenfield, Feb 23 2019

A075481 Number of iteration that first becomes smaller than the initial value if Collatz-function (A006370) is iterated, starting with numbers of form 64n+47. Corresponds to selection of every 16th term from A074474.

Original entry on oeis.org

89, 51, 14, 33, 22, 17, 14, 45, 27, 22, 14, 35, 17, 20, 14, 35, 22, 22, 14, 43, 22, 17, 14, 27, 128, 20, 14, 25, 17, 25, 14, 20, 22, 30, 14, 82, 20, 17, 14, 45, 22, 27, 14, 25, 17, 27, 14, 48, 20, 30, 14, 43, 30, 17, 14, 58, 61, 27, 14, 53, 17, 56, 14, 22, 30, 58, 14, 27, 53

Offset: 0

Labos Elemer, Sep 23 2002

nonn

Remark that initial values of form 64m+r, if r={3,11,19,27,35,43,51,55} provide first-sink-lengths {7,9,7,9,7,9,7,9} respectively; e.g. {64k+19,192k+58,96k+29,288k+88,144k+44,72k+22,36k+11} submerge first below initial value at the 7th term,36k+11<64k+19.

			n=2: 64n+47=175,list={175,526,263,790,395,1186,593,1780, 890,445,1336,668,334,167,502,251....}, i.e. the 14th term=167 is the first that <175, the initial value, so a(2)=14.

Cf. A074473, A074474, A075476-A075483, A006370.

a(n)=A075473[64n+47], n=0, ..., 256

A361733 Length of the Collatz (3x + 1) trajectory from k = 10^n - 1 to a term less than k, or -1 if the trajectory never goes below k.

Original entry on oeis.org

4, 7, 17, 12, 113, 17, 79, 22, 51, 33, 64, 35, 128, 56, 110, 53, 84, 128, 107, 115, 175, 82, 477, 172, 141, 182, 188, 110, 159, 167, 301, 206, 151, 146, 128, 195, 190, 299, 208, 276, 180, 185, 500, 203, 229, 190, 265, 270, 288, 252, 299, 208, 350, 348, 459, 330, 314, 268, 490, 361, 578

Offset: 1

Paul M. Bradley, Mar 22 2023

nonn

k = 10^n - 1 = A002283(n) is the repdigit consisting of n digits, all 9s.
The sequence seems to be chaotic but broadly increasing.
By contrast, repdigits of 1, 3, 5, or 7, have constant dropping times after a few initial values each.

			a(1) = 4 as for k = 9, the Collatz trajectory begins 9, 28, 14, 7, ...;
a(2) = 7 as for k = 99, the Collatz trajectory begins 99, 298, 149, 448, 224, 112, 56, ...;
a(3) = 17 as for k = 999, the Collatz trajectory begins 999, 2998, 1499, 4498, 2249, 6748, 3374, 1687, 5062, 2531, 7594, 3797, 11392, 5696, 2848, 1424, 712, ... .

Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A074473, A002283, A006370, A074474, A075483, A075480.

collatzLen[a_Integer] := Module[{len = 1, x = a},
  While[x >= a,    If[Mod[x, 2] > 0,
      x = 3 x + 1,
      x = Quotient[x, 2]
    ];
    len++
  ];
  Return[len]
]

f(n) = if (n%2, 3*n+1, n/2); \\ A006370
b(n) = if (n<3, return(n)); my(m=n, nb=0); while (1, m = f(m); nb++; if (m < n, return(nb+1));); \\ A074473
a(n) = b(10^n-1); \\ Michel Marcus, Mar 28 2023

def collatz_len(a):
    length = 1
    x = a
    while x >= a:
        if x % 2 > 0:
            x = 3 * x + 1
        else:
            x = x // 2
        length += 1
    return length

a(n) = A074473(10^n-1).

cp's OEIS Frontend

A074473 Dropping time for the 3x+1 problem: for n >= 2, number of iteration that first becomes smaller than the initial value if Collatz-function (A006370) is iterated starting at n; a(1)=1 by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A076227 Number of surviving Collatz residues mod 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

PARI

Formula

Extensions

A075482 Number of iteration that first becomes smaller than the initial value if Collatz-function (A006370) is iterated, starting with numbers of the form 64n + 59.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A075480 Number of iteration that first becomes smaller than the initial value if Collatz function (A006370) is iterated, starting with numbers of the form 64n + 39.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A075481 Number of iteration that first becomes smaller than the initial value if Collatz-function (A006370) is iterated, starting with numbers of form 64n+47. Corresponds to selection of every 16th term from A074474.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A361733 Length of the Collatz (3x + 1) trajectory from k = 10^n - 1 to a term less than k, or -1 if the trajectory never goes below k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula