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

A022331 Index of 2^n within sequence of numbers of form 2^i*3^j (A003586).

Original entry on oeis.org

1, 2, 4, 6, 9, 13, 17, 22, 28, 34, 41, 48, 56, 65, 74, 84, 95, 106, 118, 130, 143, 157, 171, 186, 202, 218, 235, 253, 271, 290, 309, 329, 350, 371, 393, 416, 439, 463, 487, 512, 538, 564, 591, 619, 647, 676, 706, 736, 767, 798, 830, 863, 896, 930, 965, 1000, 1036, 1072

Offset: 0

Clark Kimberling

nonn

Amiram Eldar, Table of n, a(n) for n = 0..10000 (terms 0..1000 from Zak Seidov)
Norman Carey, Lambda Words: A Class of Rich Words Defined Over an Infinite Alphabet, arXiv preprint arXiv:1303.0888 [math.CO], 2013; Lambda Words: A Class of Rich Words Defined Over an Infinite Alphabet, J. Int. Seq. 16 (2013), Article 13.3.4.

Cf. A000079, A003586, A071521, A020915 (first differences), A152747.

Cf. A022330 (index of 3^n within A003586).

c[0] = 1; c[n_] := 1 + Sum[Ceiling[j*Log[3, 2]], {j, n}]; Table[c[i], {i, 0, 60}] (* Norman Carey, Jun 13 2012 *)

a(n)=my(t=1);1+n+sum(k=1,n,logint(t*=2,3)) \\ Ruud H.G. van Tol, Nov 25 2022

from sympy import integer_log
def A022331(n):
    m = 1<Chai Wah Wu, Sep 16 2024

a(n) = A071521(A000079(n)); A003586(a(n)) = A000079(n). - Reinhard Zumkeller, May 09 2006

a(n) ~ c * n^2, where c = log(2)/(2*log(3)) (A152747). - Amiram Eldar, Apr 07 2023

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

A156301 a(n) = ceiling( n * log_3(2) ) = ceiling(n * 0.6309297535714574371...).

Original entry on oeis.org

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

Offset: 0

Jonathan Vos Post, Feb 07 2009

a(n) is the unique k such that 1/2 <= 3^a(n)/2^(n+1) < 3/2. Equality occurs iff n = 0. See Gorman-Huang and Marks.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Li an-Ping, A note on the counterfeit coins problem, arXiv:0902.0841 [math.CO], 2009-2010.
A. Gorman-Huang and E. Marks, Approximating Powers of 2 Using Powers of 3 and Break Point Rounding, Girls' Angle Bulletin, Vol. 18, No. 5 (2025), 8-10.

Cf. A020915, A102525. - R. J. Mathar, Feb 19 2009

Cf. A136409.

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

seq(ceil(n*log[3](2)),n=0..120) ; # R. J. Mathar, Mar 14 2009

With[{c=Log[3,2]},Ceiling[c*Range[0,80]]] (* Harvey P. Dale, Aug 07 2015 *)

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

More terms from R. J. Mathar, Mar 14 2009

Edited by N. J. A. Sloane, May 23 2009 at the suggestion of Hagen von Eitzen

A260683 Number of 2's in the expansion of 2^n in base 3.

Original entry on oeis.org

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

Offset: 0

Emmanuel Vantieghem, Nov 15 2015

Erdős conjectures that a(n) > 0 for n > 8.

			For n=5, the expansion of 2^n in number base 3 is 1012, thus: a(n)=1
For n=10, the expansion of 2^n in number base 3 is 1101221, thus: a(n)=2

R. K. Guy, Unsolved Problems in Number Theory, B33. [Does not seem to be in section B33.]

Robert Israel, Table of n, a(n) for n = 0..10000
Paul Erdős, Some unconventional problems in number theory, Mathematics Magazine, Vol. 52, No. 2 (1979), pp. 67-70.

Cf. A004642 (2^n in base 3), A020915 (number of terms), A036461 (number of 1's), A104320 (number of 0's).
Cf. A000108 (conjecture that A000108(n) is 6m+1 only for n = 0, 1 and 5 follows from Erdős's one).
Cf. A005836 (for numbers with no 2 in base 3).

seq(numboccur(2, convert(2^n,base,3)),n=0..100); # Robert Israel, Nov 15 2015

S={};n=-1;While[n<150,n++;A=IntegerDigits[2^n,3];k=Count[A,2];AppendTo[S, k]];S

c(k, d, b) = {my(c=0, f); while (k>b-1, f=k-b*(k\b); if (f==d, c++); k\=b); if (k==d, c++); return(c)}
for(n=0, 300, print1(c(2^n, 2, 3)", ")) \\ Altug Alkan, Nov 15 2015

a(n) = #select(x->(x==2), digits(2^n, 3)); \\ Michel Marcus, Nov 28 2018

a(n) = hammingweight(digits(2^n, 3)\2); \\ Ruud H.G. van Tol, May 09 2024

use ntheory ":all"; sub a260683 { scalar grep { $==2 } todigits(vecprod((2) x shift), 3) } # _Dana Jacobsen, Aug 16 2016

a(n) = A020915(n) - A104320(n) - A036461(n). - Altug Alkan, Nov 15 2015

a(n) = A081603(A000079(n)). - Michel Marcus, Dec 03 2015

A265210 Irregular triangle read by rows in which row n lists the base 3 digits of 2^n in reverse order, n >= 0.

Original entry on oeis.org

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

Offset: 0

L. Edson Jeffery, Dec 04 2015

The length of row n is A020915(n) = 1 + A136409(n).

Conjecture 1: The sequence in column k is periodic, with period p(k) = 2*3^(k-1) = A008776(k-1), k >= 1, and in which the numbers 0,1,2 appear with equal frequency, for each k>1.

			n
0:    1
1:    2
2:    1  1
3:    2  2
4:    1  2  1
5:    2  1  0  1
6:    1  0  1  2
7:    2  0  2  1  1
8:    1  1  1  0  0  1
9:    2  2  2  0  0  2
10:   1  2  2  1  0  1  1
11:   2  1  2  0  1  2  2
12:   1  0  2  1  2  1  2  1
13:   2  0  1  0  2  0  2  0  1
14:   1  1  2  0  1  1  1  1  2
15:   2  2  1  1  2  2  2  2  1  1

Cf. A000079 (powers of 2), A004642 (powers of 2 written in base 3), A008776 (2*3^n).
Cf. A265209 (base 3 digits of 2^n).
Cf. A264980 (row n read as ternary number).
Cf. A037096 (numbers constructed from the inverse case, base 2 digits of 3^n).

(* Replace Flatten with Grid to display the triangle: *)
Flatten[Table[Reverse[IntegerDigits[2^n, 3]], {n, 0, 15}]]

A265210_row(n)=Vecrev(digits(2^n,3)) \\ M. F. Hasler, Dec 05 2015

A022924 Number of 3^m between 2^n and 2^(n+1).

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1

Offset: 0

Clark Kimberling

nonn

This is a Sturmian sequence; consider the straight line of equation y = x*log(3)/log(2), the sequence gives the number m of integer ordinate points between the abscissa points n and n+1. - Richard Aime Blavy, Jun 14 2020

David A. Corneth, Table of n, a(n) for n = 0..9999

Cf. A136409 (partial sums).

First differences of A020915.

a(n) = logint(2^(n+1),3)-logint(2^n,3) \\ Charles R Greathouse IV, Jan 16 2017

A036461 Number of 1 digits in base 3 representation of 2^n.

Original entry on oeis.org

1, 0, 2, 0, 2, 2, 2, 2, 4, 0, 4, 2, 4, 2, 6, 4, 2, 4, 6, 2, 6, 4, 6, 4, 8, 2, 10, 4, 4, 8, 6, 8, 8, 8, 8, 6, 10, 8, 10, 10, 6, 6, 12, 8, 10, 14, 8, 10, 10, 12, 16, 8, 12, 18, 10, 10, 14, 10, 14, 14, 16, 10, 16, 12, 16, 16, 14, 16, 14, 18, 20, 12, 20, 10, 22, 12, 26, 8, 20, 12, 22, 14, 16

Offset: 0

David W. Wilson

The number of 1's in the base 3 representation of any even(odd) number is even(odd).

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A020915 (number of digits), A104320 (number of 0's), A260683 (number of 2's).

seq(numboccur(1,convert(2^n,base,3)),n=0..100); # Robert Israel, Apr 04 2018

Table[DigitCount[2^n,3,1],{n,0,120}]  (* Harvey P. Dale, Mar 14 2011 *)

a(n) = #select(x->(x==1), digits(2^n, 3)); \\ Michel Marcus, Apr 04 2018

A265209 Irregular triangle read by rows in which row n lists the base-3 digits of 2^n, n >= 0.

Original entry on oeis.org

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

Offset: 0

L. Edson Jeffery, Dec 04 2015

The length of row n is A020915(n) = 1 + A136409(n).

			Triangle begins:
  1
  2
  1  1
  2  2
  1  2  1
  1  0  1  2
  2  1  0  1
  1  1  2  0  2
  1  0  0  1  1  1
  2  0  0  2  2  2
  1  1  0  1  2  2  1
  2  2  1  0  2  1  2
  1  2  1  2  1  2  0  1
  1  0  2  0  2  0  1  0  2
  2  1  1  1  1  0  2  1  1
  1  1  2  2  2  2  1  1  2  2

Cf. A000079 (powers of 2), A003137, A004642 (powers of 2 written in base 3).

Cf. A265210 (base 3 digits of 2^n in reverse order).

(* Replace Flatten with Grid to display the triangle: *)
Flatten[Table[IntegerDigits[2^n, 3], {n, 0, 15}]]

for(n=0,15,for(k=1,#digits(2^n,3),print1(digits(2^n,3)[k],", "))) \\ Derek Orr, Dec 24 2015

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

A022331 Index of 2^n within sequence of numbers of form 2^i*3^j (A003586).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A076227 Number of surviving Collatz residues mod 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

PARI

Formula

Extensions

A156301 a(n) = ceiling( n * log_3(2) ) = ceiling(n * 0.6309297535714574371...).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Extensions

A260683 Number of 2's in the expansion of 2^n in base 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Perl

Formula

A265210 Irregular triangle read by rows in which row n lists the base 3 digits of 2^n in reverse order, n >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica