A186009 -id:A186009 - cp's OEIS frontend

A076227 Number of surviving Collatz residues mod 2^n.

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

A186107 Numerator of the frequency of the n-th dropping time in the Collatz iteration.

Original entry on oeis.org

1, 1, 1, 1, 3, 7, 3, 15, 85, 173, 119, 961, 663, 8045, 17637, 51033, 54475, 312455, 663535, 950235, 5936673, 1684037, 39993895, 87986917, 128989251, 205059181, 949737339, 2861515293, 400296173, 19018424205

Offset: 1

T. D. Noe, Feb 12 2011

The possible dropping times are in A020914. The denominators are in A186108. The cumulative frequency of the dropping time is A186109(n)/A186110(n).

			The frequencies are 1/2, 1/4, 1/16, 1/16, 3/128, 7/256, 3/256, 15/2048, 85/8192,....

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

Cf. A126241 (dropping times)

a(n) = numerator of A186009(n) / 2^A020914(n-1).

A186108 Denominator of the frequency of the n-th dropping time in the Collatz iteration.

Original entry on oeis.org

2, 4, 16, 16, 128, 256, 256, 2048, 8192, 32768, 16384, 262144, 262144, 2097152, 8388608, 16777216, 33554432, 134217728, 536870912, 1073741824, 4294967296, 2147483648, 34359738368, 137438953472, 274877906944, 274877906944, 2199023255552, 4398046511104, 1099511627776, 35184372088832

Offset: 1

T. D. Noe, Feb 12 2011

The numerators are in A186107.

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

Cf. A126241 (dropping times)

a(n) = denominator of A186009(n) / 2^A020914(n-1).

A186109 Numerator of the cumulative frequency of the dropping time in the Collatz iteration.

Original entry on oeis.org

1, 3, 13, 7, 115, 237, 15, 1935, 7825, 31473, 31711, 254649, 15957, 2050541, 8219801, 16490635, 33035745, 132455435, 530485275, 1061920785, 4253619813, 4256987887, 34095896991, 136471574881, 273072139013, 136638599097, 2187167322891, 4377196161075, 4378797345767, 35049397190341

Offset: 1

T. D. Noe, Feb 12 2011

The possible dropping times are in A020914. The denominators are in A186110. The frequency of the n-th dropping time is A186107(n)/A186108(n).

Riho Terras' classic paper about the Collatz problem shows the decimal values of 2(1-c(k)) in Table A, where c(k) is the cumulative frequency of dropping times <= k.

			The cumulative frequencies are 1/2, 3/4, 13/16, 7/8, 115/128, 237/256, 15/16, 1935/2048, 7825/8192, ... .

Index entries for sequences related to 3x+1 (or Collatz) problem
Riho Terras, A stopping time problem on the positive integers, ACTA Arith. 30 (1976), 241-252.

Cf. A126241 (dropping times).

a(n) = numerator of Sum_{k=1..n} A186009(k) / 2^A020914(k-1).

A186008 Irregular triangle T(n,k) read by rows, in which row n has the pattern of conjectured dropping times in the Collatz iteration.

Original entry on oeis.org

2, 4, 16, 12, 32, 8, 52, 128, 40, 56, 84, 136, 160, 180, 256, 60, 80, 136, 220, 288, 296, 448, 528, 636, 688, 712, 1024, 152, 232, 384, 648, 704, 788, 856, 1000, 1204, 1416, 1472, 1556, 1592, 1624, 1800, 1972, 2008, 2120, 2356, 2360, 2676, 2744, 2888, 2912, 3064, 3328, 3444, 3680, 3832, 4096

Offset: 1

T. D. Noe, Feb 09 2011

Consider A126241, the sequence of dropping times in the Collatz iteration. Only zero and the numbers in A020914 can be dropping times. The dropping times in A126241 have a definite pattern. For example, 1 appears at positions n = 2 + 2*i, for i=0,1,2,3,... Similarly, 2 appears at positions n = 5 + 4*i; 4 appears at n = 3 + 16*i; 5 appears at n = 11 + {12,32}*i; and 7 appears at 7 + {8, 52, 128}*i. In general, if we let s=A020914(r) be the r-th possible stopping time, then A126241(n) = s for n = A122442(r) + T(r)*i, where T(r) is the r-th row of this triangle.  The length of row n is A186009(n). The n-th row ends with 2^A020914(n).
The frequency of the r-th dropping time s=A020914(r) can be computed as A186009(r)/2^s. The first few frequencies are 1/2, 1/4, 1/16, 1/16, 3/128, 7/256, 3/256, 15/2048, and 85/8192.
The term "stopping time" is sometimes used instead of "dropping time", but the former usually refers to A006666.
This sequence is closely related to A177789.

			The triangle begins
2
4
16
12, 32
8, 52, 128
40, 56, 84, 136, 160, 180, 256
60, 80, 136, 220, 288, 296, 448, 528, 636, 688, 712, 1024

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010. See pp. 33, 35ff.

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

Cf. A014682, A126241, A006666, A186009.

A186110 Denominator of the cumulative frequency of the dropping time in the Collatz iteration.

Original entry on oeis.org

2, 4, 16, 8, 128, 256, 16, 2048, 8192, 32768, 32768, 262144, 16384, 2097152, 8388608, 16777216, 33554432, 134217728, 536870912, 1073741824, 4294967296, 4294967296, 34359738368, 137438953472, 274877906944, 137438953472, 2199023255552, 4398046511104, 4398046511104, 35184372088832

Offset: 1

T. D. Noe, Feb 12 2011

The numerators are in A186109. The frequency of the n-th dropping time is A186107(n)/A186108(n).

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

Cf. A126241 (dropping times)

a(n) = denominator of sum_{k=1..n} A186009(k) / 2^A020914(k-1).

A260591 a(n) is the number of odd numbers k < 2^n such that A260590(k) = n.

Original entry on oeis.org

0, 1, 0, 1, 2, 0, 3, 7, 0, 12, 0, 30, 85, 0, 173, 476, 0, 961, 0, 2652, 8045, 0, 17637, 51033, 0, 108950, 312455, 0, 663535, 0, 1900470, 5936673, 0, 13472296, 39993895, 0, 87986917, 0, 257978502, 820236724, 0, 1899474678, 5723030586, 0, 12809477536, 38036848410, 0, 84141805077, 0, 248369601964

Offset: 1

Joseph K. Horn, O. Praem, and Robert G. Wilson v, Jul 29 2015

nonn

a(n) is either 0 or about c^(n-1) with c = log(3)/log(2).
Nonzero values give A100982. - Ruud H.G. van Tol, Nov 25 2021
A close variant of this sequence, that starts at offset 0, but with a(0)=0 and a(1)=1, maps it to the count of dropping patterns of 2^n+c(2^n), with the c(2^n) as mentioned with A177789. The positions of the zeros of that variant sequence might be a close variant of A054414, again with a(0)=0 (not properly checked yet). - Ruud H.G. van Tol, Nov 28 2021
It appears that the proportion of zeros is 1-log(2)/log(3) = 36.907...%. - Jesse Randall, Oct 10 2024

			a(1) = 0 since there exists no odd number whose msa is 1;
a(2) = 1 since there is only one odd number, 5 with k=2 2k+1, with k less than 2^2 whose msa is 2;
a(3) = 0 since there exists no odd number whose msa is 3;
a(4) = 1 since there is only one number, 1, less than 2^(4+1) whose msa is 4;
a(5) = 2 since there are two numbers, 11 & 23, less than 2^(4+1) whose msa is 4; etc.

Cf. A260590, A054414, A100982, A186009, A186008, A177789, A346640.

msa[n_] := If[ OddQ@ n, (3n + 1)/2, n/2]; f[n_] := Block[{k = 2n + 1}, Length@ NestWhileList[ msa@# &, k, # >= k &] - 1]; g[n_] := Length@ Select[ Range[ 2^(n - 1)], f@# == n &]; Array[ g, 20]

a(31) onwards from Jesse Randall, Sep 09 2024

cp's OEIS Frontend

A076227 Number of surviving Collatz residues mod 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

PARI

Formula

Extensions

A186107 Numerator of the frequency of the n-th dropping time in the Collatz iteration.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A186108 Denominator of the frequency of the n-th dropping time in the Collatz iteration.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A186109 Numerator of the cumulative frequency of the dropping time in the Collatz iteration.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A186008 Irregular triangle T(n,k) read by rows, in which row n has the pattern of conjectured dropping times in the Collatz iteration.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A186110 Denominator of the cumulative frequency of the dropping time in the Collatz iteration.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A260591 a(n) is the number of odd numbers k < 2^n such that A260590(k) = n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions