A054414 -id:A054414 - cp's OEIS frontend

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

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

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

A117630 Complement of A056576.

Original entry on oeis.org

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

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)

A121384 a(n) = ceiling(n*e).

Original entry on oeis.org

0, 3, 6, 9, 11, 14, 17, 20, 22, 25, 28, 30, 33, 36, 39, 41, 44, 47, 49, 52, 55, 58, 60, 63, 66, 68, 71, 74, 77, 79, 82, 85, 87, 90, 93, 96, 98, 101, 104, 107, 109, 112, 115, 117, 120, 123, 126, 128, 131, 134, 136, 139, 142, 145, 147, 150, 153, 155, 158, 161, 164, 166

Offset: 0

Mohammad K. Azarian, Sep 06 2006

Because the difference between e=A001113 and the constant 1/(1-theta), theta = A102525, defined in A054414 is only 0.00877, the difference |a(n)-A054414(n)| increases approximately as 0.00877*n. - R. J. Mathar, Apr 14 2008

A022843(n) <= A022852(n) <= a(n). - Reinhard Zumkeller, Mar 17 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A022843, A022852.

a121384 = ceiling . (* exp 1) . fromIntegral
-- Reinhard Zumkeller, Mar 17 2015

Table[Ceiling[n * E], {n, 0, 80}] (* Vincenzo Librandi, Feb 22 2013 *)

A325913 Integers m such that there are exactly two powers of 2 between 3^m and 3^(m+1).

Original entry on oeis.org

1, 3, 5, 6, 8, 10, 11, 13, 15, 17, 18, 20, 22, 23, 25, 27, 29, 30, 32, 34, 35, 37, 39, 41, 42, 44, 46, 47, 49, 51, 52, 54, 56, 58, 59, 61, 63, 64, 66, 68, 70, 71, 73, 75, 76, 78, 80, 82, 83, 85, 87, 88, 90, 92, 94, 95, 97, 99, 100

Offset: 1

Benjamin Lombardo, Sep 08 2019

nonn

Or m such that A022921(m) = 2.

Also largest m such that 2^(m+n) > 3^m. - Bob Selcoe, Dec 19 2021

			For m=3, there are exactly two powers of 2 between 3^3 = 27 and 3^(3+1) = 81: 32 and 64, since 27 < 32 < 64 < 81. Therefore, m=3 is an element of the sequence (at n=2).

Benjamin Lombardo, Table of n, a(n) for n = 1..1000

Cf. A022921, A054414.

import math
def a(n):
    return math.floor(n/(math.log2(3)-1))
for n in range(1, 101):
    print("a(" + str(n) + ") = " + str(a(n)))

a(n) = floor(n/(log_2(3)-1)).

a(n) = A054414(n) - n - 1.

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

Original entry on oeis.org

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

Offset: 0

Ruud H.G. van Tol, Jan 25 2024

Highest k with 3^(n+k) <= 4^n * 2^k.

Cf. A054414, A117630, A325913, A369522 (slope).

Table[Floor[n*Log[4/3]/Log[3/2]],{n,0,68}] (* James C. McMahon, Jan 27 2024 *)

alist(N) = my(a=-1, b=1, k=0); vector(N, i, a+=2; b*=3; if(logint(b, 2) < a, a++; b*=3; k++); k); \\ note that i is n+1

a(n) = floor(n * log(3) / log(3/2)) - 2*n.
a(n) = floor(n * arctanh(1/7) / arctanh(1/5)).
a(n) = A325913(n) - n.
a(n) = A117630(n) - 2*n.
a(n) = A054414(n) - 2*n - 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

A333355 Number of bits in binary expansion of n minus the number of digits of n when written in base 3.

Original entry on oeis.org

0, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2

Offset: 1

Frank Ellermann, Mar 15 2020

Record highs are at n = 2^A054414. All n=2^k >= 2 are increases, all n=3^j are decreases, and there is either one or none 3^j between 2^(k-1) and 2^k. When one, a(2^k) = a(2^(k-1)) so not a record high. When none, a(2^k) = a(2^(k-1)) + 1 which is a record high. If 2^k and 2^(k-1) are the same length in ternary then there is no 3^j between them. This is when 2^k has most significant ternary digit 2 since 2^(k-1) >= 3^j is 2^k >= 2*3^j. These k are A054414. Non-record increases are at its complement n = 2^A020914 >= 2. - Kevin Ryde, Apr 04 2020

			a(8) = 2 = 4 - 2 for binary 1000 and ternary 22.
a(64) = 3 = 7 - 4 for binary 1000000 and ternary 2101.

Cf. A007088 ( binary), A000523 (floor(log_2(n))), A029837.

Cf. A007089 (ternary), A062153 (floor(log_3(n))), A117966.

a:= n-> ilog[2](n)-ilog[3](n):
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 15 2020

a[n_]: = Floor @ Log[2, n] - Floor @ Log[3, n]; Array[a, 100] (* Amiram Eldar, Mar 16 2020 *)

a(n) = logint(n,2) - logint(n,3); \\ Kevin Ryde, May 15 2020

L = 1 ;  M = 1 ;  B = 2 ;  T = 3       ;  S = 0
do N = 2 while length( S ) < 258
   if B = N then  do    ;  B = B * 2   ;  L = L + 1   ;  end
   if T = N then  do    ;  T = T * 3   ;  M = M + 1   ;  end
   S = S || ',' L - M
end N
say S                   ;  return S

a(n) = A000523(n) - A062153(n) = floor(log_2(n)) - floor(log_3(n)).

a(n) = length(A007088(n)) - length(A007089(n)).

cp's OEIS Frontend

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

A076227 Number of surviving Collatz residues mod 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

PARI

Formula

Extensions

A117630 Complement of A056576.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A121384 a(n) = ceiling(n*e).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A325913 Integers m such that there are exactly two powers of 2 between 3^m and 3^(m+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

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

Views