A020914 -id:A020914 - cp's OEIS frontend

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

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

A054414 a(n) = 1 + floor(n/(1-log(2)/log(3))).

Original entry on oeis.org

1, 3, 6, 9, 11, 14, 17, 19, 22, 25, 28, 30, 33, 36, 38, 41, 44, 47, 49, 52, 55, 57, 60, 63, 66, 68, 71, 74, 76, 79, 82, 84, 87, 90, 93, 95, 98, 101, 103, 106, 109, 112, 114, 117, 120, 122, 125, 128, 131, 133, 136, 139, 141, 144, 147, 150, 152, 155, 158, 160, 163

Offset: 0

B. Schaaf (m.m.schaaf-visch(AT)wxs.nl), May 20 2000

These numbers appear in connection with the 3x+1 problem.
Also, numbers n such that the first digit in ternary expansion on 2^n is 2. N. J. A. Sloane conjectured that, for any integer n >=15, 2^n always has a 0 in its ternary expansion. - Mohammed Bouayoun (Mohammed.bouayoun(AT)sanef.com), Apr 24 2006
Except for 1, this is the complement of A020914 and therefore these two form a pair of Beatty sequences. - Robert G. Wilson v, May 25 2014

			a(5) = 1 + floor(5/(1-log(2)/log(3)))= 1 + floor(5/0.3690702464...)= 1 + floor(13.54...) = 14.

Cf. A020914.

Digits := 500: it := evalf(ln(2)/ln(3)): for n from 0 to 200 do printf(`%d,`,1+floor(n/(1-it))) od:

Do[If[First[IntegerDigits[2^n, 3]] == 2, Print[n]], {n, 1, 200}] (* Mohammed Bouayoun (Mohammed.bouayoun(AT)sanef.com), Apr 24 2006 *)
f[n_]:=Floor[1+n/(1-(Log[2]/Log[3]))];Array[f,105] (* Robert G. Wilson v, May 25 2014 *)

alist(N) = my(a=1/2, b=1, r=-1); vector(N, i, a*=4; b*=3; r+=2; if(a>b, a*=2; b*=3; r++); r); \\ Ruud H.G. van Tol, Jan 21 2024 (with help from the pari-users mailing list)

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

# faster for initial segment of sequence
from itertools import islice
def agen(): # generator of terms, after Ruud H.G. van Tol
    a, b, r = 2, 3, 1
    while True:
        yield r
        a <<= 2; b *= 3; r += 2
        if a > b: a <<= 1; b *= 3; r += 1
print(list(islice(agen(), 100))) # Michael S. Branicky, Oct 10 2024

a(n) = 1 + floor(n * r), with r = log(3) / log(3/2) = 2.709511... - Ruud H.G. van Tol, May 09 2024

More terms from James Sellers, May 23 2000

Erroneous formula a(n) =? A083088(n) + n - 1 deleted Jan 30 2008

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

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)

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).

A190000 a(n) = n + [nr/s] + [nt/s]; r=1, s=sinh(1), t=cosh(1).

Original entry on oeis.org

2, 5, 8, 12, 15, 18, 21, 24, 27, 31, 34, 37, 41, 43, 46, 50, 53, 56, 59, 63, 65, 68, 72, 75, 78, 82, 84, 87, 91, 94, 97, 101, 104, 106, 109, 113, 116, 119, 123, 126, 128, 132, 135, 138, 142, 145, 147, 151, 154, 157, 160, 164, 167, 169, 173, 176, 179, 183, 186, 189, 192, 195, 198, 202, 205, 208, 211, 214, 217, 220, 224, 227, 230, 233

Offset: 1

Clark Kimberling, May 03 2011

nonn

See A189999.

Does the growth of a(n) oscillate with A020914(2*n-1), or does one sequence eventually outgrow the other? - Jeffrey R. Goodwin, Aug 26 2011

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A189999, A190001.

[n + Floor(n/Sinh(1)) + Floor(n/Tanh(1)): n in [1..100]]; // G. C. Greubel, Jan 11 2018

r=1; s=Sinh[1]; t=Cosh[1];
a[n_] := n + Floor[n*s/r] + Floor[n*t/r];
b[n_] := n + Floor[n*r/s] + Floor[n*t/s];
c[n_] := n + Floor[n*r/t] + Floor[n*s/t];
Table[a[n], {n, 1, 120}]  (* A189999 *)
Table[b[n], {n, 1, 120}]  (* A190000 *)
Table[c[n], {n, 1, 120}]  (* A190001 *)

for(n=1,100, print1(n + floor(n/sinh(1)) + floor(n/tanh(1)), ", ")) \\ G. C. Greubel, Jan 11 2018

A189999:  a(n) = n + [n*sinh(1)] + [n*cosh(1)].
A190000:  b(n) = n + [n*csch(1)] + [n*coth(1)].
A190001:  c(n) = n + [n*sech(1)] + [n*tanh(1)].

A122790 Decimal expansion of Wagon's constant: the average "dropping time" of the Collatz (3x+1) iteration.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Sep 11 2006

Cf. A060445 (dropping time of the 3x+1 iteration starting at 2n+1), A100982, A122791.

Sum_{k>0} A122437(k+1)*A100982(k)/2^(A020914(k)-1) = 9.47795555655927473691668101258904...

cp's OEIS Frontend

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

A054414 a(n) = 1 + floor(n/(1-log(2)/log(3))).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions

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

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

A190000 a(n) = n + [nr/s] + [nt/s]; r=1, s=sinh(1), t=cosh(1).