A156301 -id:A156301 - 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

A136409 a(n) = floor(n*log_3(2)).

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 10, 10, 11, 11, 12, 13, 13, 14, 15, 15, 16, 17, 17, 18, 18, 19, 20, 20, 21, 22, 22, 23, 23, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 41, 41, 42, 42, 43, 44, 44, 45, 46, 46

Offset: 0

Ctibor O. Zizka, Mar 31 2008

a(n) is the exponent of the greatest power of 3 not exceeding 2^n.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Titu Andreescu and Dorin Andrica, On a class of sums involving the floor function, Mathematical Reflections 3, 2006.
H. W. Gould and Jocelyn Quaintance, Floor and Roof Function Analogs of the Bell Numbers, INTEGERS: El. J. Comb. Number Theory 7 (2007), #A58.

Cf. A102525, A156301.

a136409 = floor . (* logBase 3 2) . fromIntegral
-- Reinhard Zumkeller, Jul 03 2015

With[{k = Log[3, 2]}, Array[Floor[k #] &, 75, 0]] (* Michael De Vlieger, Sep 29 2019 *)

a(n)=logint(2^n,3) \\ Charles R Greathouse IV, Sep 02 2015

from sympy import integer_log
def A136409(n): return integer_log(1<Chai Wah Wu, Oct 09 2024

From Benjamin Lombardo, Sep 08 2019: (Start)
a(A020914(k)) = k.
a(A054414(k)) = a(A054414(k)-1) for k > 0. (End)

A160511 Number of weighings needed to find lighter coins among n coins.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 18, 18, 19

Offset: 1

Hagen von Eitzen, May 16 2009

a(n) is the minimal worst-case number of weighings needed by an algorithm to sort a set of n coins of two possible weights into heavy vs. light coins by using a balance; additional known good (heavy, say) coins are available (esp. to distinguish "all heavy" from "all light").

It is known that ceiling(n*log_3(2) + log_3(135/128)) <= a(n) <= ceiling(7n/11) for all n except for n=3. This implies 19 <= a(30) <= 20 and in fact a(n) = ceiling(7n/11) for several n <= 187, esp. for all n with n <= 50 except n=3, n=30, n=41, n=49.

			For n=1, compare the given coin A with a known heavy coin X. If A < X, then A is a light coin; if A=X, then A is a heavy coin; the outcome A > X is not possible. Since one weighing was needed, we have a(1)=1.
For n=3, to sort coins A,B,C, one optimal algorithm is: First compare A:B. If A < B, we know that A is light and B is heavy and can find out about C by comparing, e.g., B:C in a second weighing. The case A > B is symmetric. If, however, A=B, compare A:C. If A < C, we know that A,B are light and C is heavy and vice versa for A > C. The worst case is A=C, which requires a third weighing, e.g., A:X, against a known heavy coin X. Since no algorithm exists that never uses more than 2 weighings, we have a(3) = 3.

An-Ping Li, A note on the counterfeit coins problem, arXiv:0902.0841v8 [math.CO]

Cf. A156301. - Jonathan Vos Post, May 18 2009

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

A136409 a(n) = floor(n*log_3(2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A160511 Number of weighings needed to find lighter coins among n coins.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs