A056576 -id:A056576 - cp's OEIS frontend

A117630 Complement of A056576.

2, 5, 8, 10, 13, 16, 18, 21, 24, 27, 29, 32, 35, 37, 40, 43, 46, 48, 51, 54, 56, 59, 62, 65, 67, 70, 73, 75, 78, 81, 83, 86, 89, 92, 94, 97, 100, 102, 105, 108, 111, 113, 116, 119, 121, 124, 127, 130, 132, 135, 138, 140, 143, 146, 149, 151, 154, 157, 159, 162, 165

Offset: 1

Robert G. Wilson v, Apr 08 2006

nonn

A Beatty sequence.

Robert Israel, Table of n, a(n) for n = 1..10000
Index entries for sequences related to Beatty sequences

Cf. A054414, A056576.
Cf. A102525 (decimal expansion of log_3(2)).
Cf. A254312 (sequence arises as exponents in array definition).

[Floor(n*Log(3)/Log(3/2)): n in [1..80]]; // Vincenzo Librandi, Apr 17 2015

seq(floor(n*log[3/2](3)), n=1..100); # Robert Israel, Nov 09 2015

Mathematica
```
Table[Floor[n*Log[3/2, 3]], {n, 61}]
```

vector(100, n, floor(n*log(3)/log(3/2))) \\ Altug Alkan, Nov 10 2015

from operator import sub
from sympy import integer_log
def A117630(n):
    def f(x): return n+sub(*integer_log(1<Chai Wah Wu, Oct 09 2024

a(n) = floor(n*log(3)/log(3/2)).

a(n) = A054414(n) - 1. - Ruud H.G. van Tol, May 10 2024

A293308 Number of permutations of zero-one words with A056576(n)-n zeros and n-1 ones.

Original entry on oeis.org

1, 2, 3, 10, 15, 56, 210, 330, 1287, 2002, 8008, 31824, 50388, 203490, 319770, 1307504, 2042975, 8436285, 34597290, 54627300, 225792840, 354817320, 1476337800, 6107086800, 9669554100, 40225345056, 63432274896, 265182149218, 416714805914, 1749695026860

Offset: 1

Frank Ellermann, Oct 05 2017

nonn

			a(4) = 5! / ( 2! * 3! ) = 5*4/2 = 10.
From _Mike Winkler_, Oct 30 2017: (Start)
The next table shows the output using the PARI function NextPermutation(a), (cf. PROG)
[0, 0, 1, 1, 1] 1
[0, 1, 0, 1, 1] 2
[0, 1, 1, 0, 1] 3
[0, 1, 1, 1, 0] 4
[1, 0, 0, 1, 1] 5
[1, 0, 1, 0, 1] 6
[1, 0, 1, 1, 0] 7
[1, 1, 0, 0, 1] 8
[1, 1, 0, 1, 0] 9
[1, 1, 1, 0, 0] 10
(End)

Michael De Vlieger, Table of n, a(n) for n = 1..2211
Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], Sep 2017. [see (17) on p. 9]

Cf. A056576, A100982.

Table[(# - 1)!/((# - n)!*(n - 1)!) &@ Floor[n Log[2, 3]], {n, 30}] (* Michael De Vlieger, Oct 06 2017 *)

/* method used in the linked paper arXiv:1709.03385 */
NextPermutation(a) = {i=#a-1; while(!(i<1 || a[i]a[i]), k--); t=a[k]; a[k]=a[i]; a[i]=t; for(k=i+1, (#a+i)/2, t=a[k]; a[k]=a[#a+1+i-k]; a[#a+1+i-k]=t); return(a)}
  /* example for n = 4 */
  {j=1; a=[0, 0, 1, 1, 1]; until(a==0, print(a" "j); j++; a=NextPermutation(a))} \\ Mike Winkler, Oct 30 2017

a(n) = ( A056576(n) - 1 )! / ( ( A056576(n) - n )! * ( n - 1)! )

A020914 Number of digits in the base-2 representation of 3^n.

Original entry on oeis.org

1, 2, 4, 5, 7, 8, 10, 12, 13, 15, 16, 18, 20, 21, 23, 24, 26, 27, 29, 31, 32, 34, 35, 37, 39, 40, 42, 43, 45, 46, 48, 50, 51, 53, 54, 56, 58, 59, 61, 62, 64, 65, 67, 69, 70, 72, 73, 75, 77, 78, 80, 81, 83, 85, 86, 88, 89, 91, 92, 94, 96, 97, 99, 100, 102, 104, 105, 107

Offset: 0

Clark Kimberling

Also, numbers k such that the first digit in the ternary expansion of 2^k is 1. - Mohammed Bouayoun (Mohammed.bouayoun(AT)sanef.com), Apr 24 2006
a(n) is the smallest integer such that n/a(n) < log_2(3). - Trevor G. Hyde (thyde12(AT)amherst.edu), Jul 31 2008
This sequence represents allowable values of the "dropping time" in the Collatz (3x+1) problem when iterated according to the function f(n) := n/2 if n is even, (3n+1)/2 otherwise, as tabulated in A126241. There is one exception, A126241(1), which has been set to zero by convention. - K. Spage, Oct 22 2009
An integer k is a term of A020914 if and only if floor(k*(1 + log(2)/log(3))) - abs(k-1)*(1 + log(2)/log(3)) - 1 >= 0. - K. Spage, Oct 22 2009
Also smallest k such that ceiling(2^k / 3^n) = 2. - Michel Lagneau, Jan 31 2012
For n > 0, first differences of A022330. - Michel Marcus, Oct 03 2013
Also the number of powers of two less than or equal to 3^n. - Robert G. Wilson v, May 25 2014
Except for 1, A020914 is the complement of A054414 and therefore these two form a pair of Beatty sequences. - Robert G. Wilson v, May 25 2014

T. D. Noe, R. J. Mathar, Table of n, a(n) for n = 0..20000
Mike Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences, 2014.
Mike Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015.
Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.

Cf. A056576, A054414, A070939, A000244, A227048, A022330, A022921 (first differences), A126241.
Cf. A020857 (decimal expansion of log_2(3)).
Cf. A020915.
Cf. A204399 (essentially the same).

a020914 = a070939 . a000244  -- Reinhard Zumkeller, Jun 30 2013

A020914 :=n->nops(convert(3^n,base,2)):
seq(A020914(n),n=0..70); # Emeric Deutsch, Apr 30 2006
seq(ilog2(3^n)+1, n=0 .. 100); # Robert Israel, Dec 12 2014

Table[Length[IntegerDigits[3^n, 2]], {n, 0, 100}] (* Stefan Steinerberger, Apr 19 2006 *)
a[n_] := Floor[ Log2[3^n] + 1]; Array[a, 105, 0] (* Robert G. Wilson v, May 25 2014 *)

for(n=0,100,print1(floor(1+n*log(3)/log(2)),",")) \\ K. Spage, Oct 22 2009

a(n)=exponent(3^n)+1 \\ Charles R Greathouse IV, Nov 03 2022

def A020914(n): return (3**n).bit_length() # Chai Wah Wu, Oct 09 2024

a(n) = floor(1 + n*log(3)/log(2)). - K. Spage, Oct 22 2009
a(0) = 1, a(n+1) = a(n) + A022921(n). - K. Spage, Oct 23 2009
a(n) = A122437(n-1) - n. - K. Spage, Oct 23 2009
A098294(n) = a(n) + n for n > 0. - Mike Winkler, Dec 31 2010
a(n) = A070939(A000244(n)) = length of n-th row in triangle A227048. - Reinhard Zumkeller, Jun 30 2013
a(n) = 1 + floor(n*log_2(3)) = 1 + A056576(n) = 1 + floor(n*A020857). - L. Edson Jeffery, Dec 12 2014
A020915(a(n)) = n + 1. - Reinhard Zumkeller, Mar 28 2015

More terms from Stefan Steinerberger, Apr 19 2006

A100982 Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant.

Original entry on oeis.org

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

Offset: 1

Steven Finch, Jan 13 2005

Eric Roosendaal counted all admissible sequences up to order j=1000 (2005). Note: there is a typo in both Wagon and Chamberland in the definition of Wagon's constant 9.477955... The expression floor(1 + 2*i + i*log_2(3)) should be replaced by floor(1 + i + i*log_2(3)).
The length of all admissible sequences of order j is A020914(j). - T. D. Noe, Sep 11 2006
Conjecture: a(n) is given for each n > 3 by a formula using a(2)..a(n-1). This allows us to create an iterative algorithm which generates a(n) for each n > 6. This has been proved for each n <= 53. For higher values of n the algorithm must be slightly modified. - Mike Winkler, Jan 03 2018
Theorem 1: a(k) is given for each k > 1 by a formula using a(1)..a(k-1). Namely, a(1)=1 and a(k+1) = Sum_{m=1..k} (-1)^(m-1)*binomial(floor((k-m+1)*(log(3)/log(2))) + m - 1, m)*a(k-m+1) for k >= 1. - Vladimir M. Zarubin, Sep 25 2015
Theorem 2: 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 connection with A076227, A056576 and A022921. - Mike Winkler, Sep 12 2017
A177789 shows another theorem and algorithm for generating a(n). - Mike Winkler, Sep 12 2017

			The unique admissible sequence of order 1 is 3/2, 1/2.
The unique admissible sequence of order 2 is 3/2, 3/2, 1/2, 1/2.
The two admissible sequences of order 3 are 3/2, 3/2, 3/2, 1/2, 1/2 and 3/2, 3/2, 1/2, 3/2, 1/2.
a(13) = 8045 = binomial(floor(5*(13-2)/3), 13-2)
- Sum_{i=2..6} binomial(floor((3*(13-i)+0)/2), 13-i)*a(i)
- Sum_{i=7..11} binomial(floor((3*(13-i)-1)/2), 13-i)*a(i)
- Sum_{i=12..12} binomial(floor((3*(13-i)-2)/2), 13-i)*a(i)
= 31824 - 4368*1 - 3003*2 - 715*3 - 495*7 - 120*12 - 28*30 - 21*85 - 5*173 - 4*476 - 1*961 - 0*2652. (Conjecture)
From _Mike Winkler_, Sep 12 2017: (Start)
The next table shows how Theorem 2 works. No entry is equal to zero.
n =       3  4  5   6   7   8   9  10  11   12 .. |A076227(k)=
--------------------------------------------------|
k =  2 |  1                                       |     1
k =  3 |  1  1                                    |     2
k =  4 |     2  1                                 |     3
k =  5 |        3   1                             |     4
k =  6 |        3   4   1                         |     8
k =  7 |            7   5   1                     |    13
k =  8 |               12   6   1                 |    19
k =  9 |               12  18   7   1             |    38
k = 10 |                   30  25   8   1         |    64
k = 11 |                   30  55  33   9    1    |   128
:      |                        :   :   :    : .. |    :
--------------------------------------------------|---------
a(n) =    2  3  7  12  30  85 173 476 961 2652 .. |
The entries (k,n) in this table are generated by the rule (k+1,n) = (k,n) + (k,n-1). The last value of (k+1,n) is given by k+1 = A056576(n-1), or the highest value in column n is given twice only if A022921(n-2) = 2. Then a(n) is equal to the sum of the entries in column n. For n = 7 there is 1 = 0 + 1, 5 = 1 + 4, 12 = 5 + 7, 12 = 12 + 0. Therefore a(7) = 1 + 5 + 12 + 12 = 30. The sum of row k is equal to A076227(k). (End)
From _Ruud H.G. van Tol_, Dec 04 2023: (Start)
A tree view.
n-tree--A098294--ids-----paths-----------------a(n)
0 ._          0  0       0                       -
1 |_          1  1       10                      1
2 |_._        2  2       1100                    1
3 |_|_        2  3-4     11010     -   11100     2
4 |_|_._      3  5-7     1101100   -  1111000    3
5 |_|_|_      3  8-14    11011010  - 11111000    7
6 |_|_|_._    4  15-26   1101101100-1111110000  12
7 |_|_|_|_._  5  27-56   ...                    30
8 |_|_|_|_|_  5  57-141  ...                    85
...
For n>=1, the endpoints are at A098294(n) to the right.
(End)

T. D. Noe, Table of n, a(n) for n = 1..500
M. Chamberland, Una actualizacio del problema 3x+1, Butl. Soc. Catalana Mat. 18 (2003) 19-45.
M. Chamberland, English translation
Ruud H.G. van Tol, Sequence as counts of lattice walks
Ruud H.G. van Tol, A100982 Musings
Stan Wagon, The Collatz problem, Math. Intelligencer 7 (1985) 72-76.
Mike Winkler, On a stopping time algorithm of the 3n + 1 function, 2011.
Mike Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence, arXiv:1412.0519 [math.GM], 2014.
Mike Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015.
Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.

Cf. A122790 (Wagon's constant), A076227, A056576, A022921, A098294, A177789.

Cf. A060941, A293946.

(* based on Eric Roosendaal's algorithm *) nn=100; Clear[x,y]; Do[x[i]=0, {i,0,nn+1}]; x[1]=1; t=Table[Do[y[cnt]=x[cnt]+x[cnt-1], {cnt,p+1}]; Do[x[cnt]=y[cnt], {cnt,p+1}]; admis=0; Do[If[(p+1-cnt)*Log[3]T. D. Noe, Sep 11 2006 *)

/* translation of the above code from T. D. Noe */
{limit=100; n=1; x=y=vector(limit+1); x[1]=1; for(b=2, limit, for(c=2, b+1, y[c]=x[c]+x[c-1]); for(c=2, b+1, x[c]=y[c]); a_n=0; for(c=1, b+1, if((b+1-c)*log(3)Mike Winkler, Feb 28 2015

/* algorithm for the Conjecture */
{limit=53; zn=vector(limit); zn[2]=1; zn[3]=2; zn[4]=3; zn[5]=7; zn[6]=12; f=1; e1=-1; e2=-2; for(n=7, limit, m=floor((n-1)*log(3)/log(2))-(n-1); j=(m+n-2)!/(m!*(n-2)!); if(n>6*f, if(frac(n/2)==0, e=e1, e=e2)); if(frac((n-6 )/12)==0, f++; e1=e1+2); if(frac((n-12)/12)==0, f++; e2=e2+2); Sum=a=b=0; c=1; d=5; until(c>=n-1, for(i=2+a*5+b, 1+d+a*5, if(i>11 && frac((i+2)/6)==0, b++); delta=e-a; Sum=Sum+binomial(floor((3*(n-i)+delta)/2),n-i)*zn[i]; c++); a++; for(k=3, 50, if(n>=k*6 && a==k-1, d=k+3))); zn[n]=j-Sum; print(n" "zn[n]))} \\ Mike Winkler, Jan 03 2018

/* cf. code for Theorem 2 */
{limit=100; /*or limit>100*/ p=q=vector(limit); c=2; w=log(3)/log(2); for(n=3, limit, p[1]=Sum=1; for(i=2, c, p[i]=p[i-1]+q[i]; Sum=Sum+p[i]); a_n=Sum; print(n" "a_n); for(i=1, c, q[i]=p[i]); d=floor(n*w)-floor((n-1)*w); if(d==2, c++)); } \\ Mike Winkler, Apr 14 2015

/* algorithm for Theorem 1 */
n=20; a=vector(n); log32=log(3)/log(2);
{a[1]=1; for ( k=1, n-1, a[k+1]=sum( m=1,k,(-1)^(m-1)*binomial( floor( (k-m+1)*log32)+m-1,m)*a[k-m+1] ); print(k" "a[k]) );
} \\ Vladimir M. Zarubin, Sep 25 2015

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

A sequence s(k), where k=1, 2, ..., n, is *admissible* if it satisfies s(k)=3/2 exactly j times, s(k)=1/2 exactly n-j times, s(1)*s(2)*...*s(n) < 1 but s(1)*s(2)*...*s(m) > 1 for all 1 < m < n.
a(n) = (m+n-2)!/(m!*(n-2)!) - Sum_{i=2..n-1} binomial(floor((3*(n-i)+b)/2), n-i)*a(i), where m = floor((n-1)*log_2(3))-(n-1) and b assumes different integer values within the sum at intervals of 5 or 6 terms. (Conjecture)
a(n) = Sum_{k=n-1..A056576(n-1)} (k,n). (Theorem 2, cf. example)
a(k) = 2*A076227(A020914(k)-1) - A076227(A020914(k)), for k > 0. - Vladimir M. Zarubin, Sep 29 2019
a(1)=1, a(n) = Sum_{k=0..A020914(n-1)-n-2} A325904(k)*binomial(A020914(n-1)-k-2, n-2) for n>1. - Benjamin Lombardo, Oct 18 2019

Two more terms from Jules Renucci (jules.renucci(AT)wanadoo.fr), Nov 02 2005

More terms from T. D. Noe, Sep 11 2006

A022921 Number of integers m such that 3^n < 2^m < 3^(n+1).

Original entry on oeis.org

1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1

Offset: 0

Clark Kimberling

Represents increments between successive terms of allowable dropping times in the Collatz (3x+1) problem. That is, a(n) = A020914(n+1) - A020914(n). - K. Spage, Oct 23 2009

			From _Amiram Eldar_, Mar 01 2024: (Start)
a(0) = 1 because 3^0 = 1 < 2^1 = 2 < 3^1 = 3.
a(1) = 2 because 3^1 = 3 < 2^2 = 4 < 2^3 = 8 < 3^2 = 9.
a(2) = 1 because 3^2 = 9 < 2^4 = 16 < 3^3 = 27. (End)

T. D. Noe, Table of n, a(n) for n = 0..1000
Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.

Cf. A020914, A056576, A076227, A100982, A122437.

See also A020857 (decimal expansion of log_2(3)).

Digits := 100: c1 := log(3.)/log(2.): A022921 := n->floor((n+1)*c1)-floor(n*c1);
seq(ilog2(3^(n+1)) - ilog2(3^n), n=0 .. 1000); # Robert Israel, Dec 11 2014

i2 = 1; Table[p = i2; While[i2++; 2^i2 < 3^(n + 1)]; i2 - p, {n, 0, 98}] (* T. D. Noe, Feb 28 2014 *)
f[n_] := Floor[ Log2[ 3^n] + 1]; Differences@ Array[f, 106, 0] (* Robert G. Wilson v, May 25 2014 *)

a(n) = logint(3^(n+1),2) - logint(3^n,2) \\ Ruud H.G. van Tol, Dec 28 2022

Vec(matreduce([logint(2^i,3)|i<-[1..158]])[,2])[1..-2] \\ Ruud H.G. van Tol, Dec 29 2022

a(n) = floor((n+1)*log_2(3)) - floor(n*log_2(3)).
a(n) = A122437(n+2) - A122437(n+1) - 1. - K. Spage, Oct 23 2009
First differences of A020914. - Robert G. Wilson v, May 25 2014
First differences of A056576. - L. Edson Jeffery, Dec 12 2014
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = log_2(3) (A020857). - Amiram Eldar, Mar 01 2024

A056577 Difference between 3^n and highest power of 2 less than or equal to 3^n.

Original entry on oeis.org

0, 1, 1, 11, 17, 115, 217, 139, 2465, 3299, 26281, 46075, 7153, 545747, 588665, 5960299, 9492289, 62031299, 118985033, 88519643, 1339300753, 1870418611, 14201190425, 25423702091, 7551629537

Offset: 0

Henry Bottomley, Jun 29 2000

nonn

a(n) = A227048(n,1). - Reinhard Zumkeller, Jun 30 2013

			a(3)=11 because 3^3 = 27 and 27 - 16 = 11.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Cf. A000244, A056576, A063005, A227048.

a056577 = head . a227048_row  -- Reinhard Zumkeller, Jun 30 2013

Table[# - 2^Floor@ Log2@ # &[3^n], {n, 0, 24}] (* Michael De Vlieger, Sep 30 2017 *)

a(n) = 3^n - 2^floor(log_2(3^n)) = A000244(n) - 2^A056576(n).

A227048 Irregular triangle read by rows: row n, for n >= 0, lists the nonnegative differences 3^n - 2^m, m >= 0, in increasing order.

Original entry on oeis.org

0, 1, 2, 1, 5, 7, 8, 11, 19, 23, 25, 26, 17, 49, 65, 73, 77, 79, 80, 115, 179, 211, 227, 235, 239, 241, 242, 217, 473, 601, 665, 697, 713, 721, 725, 727, 728, 139, 1163, 1675, 1931, 2059, 2123, 2155, 2171, 2179, 2183, 2185, 2186, 2465, 4513, 5537, 6049, 6305

Offset: 0

Reinhard Zumkeller, Jun 29 2013

A020914(n) = length of n-th row;
T(n,1) = A056577(n);
T(n,A098294(n)) = A001047(n);
T(n,A020914(n)) = A024023(n);
T(n,k) = A196486(n,A020914(n)-k) for n > 0, k = 1..A056576(n).

			Initial rows:
0:  0
1:  1,2
2:  1,5,7,8
3:  11,19,23,25,26 (= 27-16, 27-8, 27-4, 27-2, 27-1)
4:  17,49,65,73,77,79,80
5:  115,179,211,227,235,239,241,242
6:  217,473,601,665,697,713,721,725,727,728
7:  139,1163,1675,1931,2059,2123,2155,2171,2179,2183,2185,2186
8:  2465,4513,5537,6049,6305,6433,6497,6529,6545,6553,6557,6559,6560
...

Reinhard Zumkeller, Rows n = 0..100 of triangle, flattened

Cf. A000079, A000244, A192111.

See also A001047, A020914, A024023, A056576, A056577, A098294, A196486.

a227048 n k = a227048_tabf !! n !! (k-1)
a227048_row n = a227048_tabf !! n
a227048_tabf = map f a000244_list  where
   f x = reverse $ map (x -) $ takeWhile (<= x) a000079_list

Definition revised by N. J. A. Sloane, Oct 11 2019

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

cp's OEIS Frontend

A117630 Complement of A056576.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A293308 Number of permutations of zero-one words with A056576(n)-n zeros and n-1 ones.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A020914 Number of digits in the base-2 representation of 3^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A100982 Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

PARI

Formula

Extensions

A022921 Number of integers m such that 3^n < 2^m < 3^(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A056577 Difference between 3^n and highest power of 2 less than or equal to 3^n.

Views

Author

Keywords

Comments

Examples

Links