OFFSET
1,3
COMMENTS
Or, ceiling(log_2(n)).
Worst-case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1).
Let x(0) = n > 1 and x(k + 1) = x(k) - floor(x(k)/2), then a(n) is the smallest integer such that x(a(n)) = 1. - Benoit Cloitre, Aug 29 2002
Also number of division steps when going from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard, Mar 25 2003
Number of ways to write n as (x + 2^y), x >= 0. Number of ways to write n + 1 as 2^x + 3^y (cf. A004050). - Benoit Cloitre, Mar 29 2003
The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
Partial sums of A209229; number of powers of 2 not greater than n. - Reinhard Zumkeller, Mar 07 2012
Also the bipartite dimension of the cocktail party graph and the complete graph K_n. - Eric W. Weisstein, Jun 29 2026
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
Cino Hilliard, The x+1 conjecture [broken link]
Lionel Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Eric Weisstein's World of Mathematics, Bipartite Dimension.
Eric Weisstein's World of Mathematics, Bit Length.
Eric Weisstein's World of Mathematics, Cocktail Party Graph.
Eric Weisstein's World of Mathematics, Complete Graph.
FORMULA
a(n) = ceiling(log_2(n)).
a(1) = 0; for n > 1, a(2n) = a(n) + 1, a(2n + 1) = a(n) + 1. Alternatively, a(1) = 0; for n > 1, a(n) = a(ceiling(n/2)) + 1. [corrected by Ilya Gutkovskiy, Mar 21 2020]
a(n) = k such that n^(1/k - 1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k - 1) < n < 2^k. - Amarnath Murthy, May 06 2001
G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - Ralf Stephan, Apr 13 2002
A062383(n-1) = 2^a(n). - Johannes W. Meijer, Jul 06 2009
a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
a(n+1) = A113473(n). - Michael Somos, Jun 02 2019
EXAMPLE
a(1) = 0, since log_2(1) = 0.
a(2) = 1, since log_2(2) = 1.
a(3) = 2, since log_2(3) = 1.58...
a(n) = 7 for n = 65, 66, ..., 127, 128.
G.f. = x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + ... - Michael Somos, Jun 02 2019
MAPLE
a:= n-> (p-> p+`if`(2^p<n, 1, 0))(ilog2(n)):
seq(a(n), n=1..120); # Alois P. Heinz, Mar 18 2013
MATHEMATICA
a[n_] := Ceiling[Log[2, n]]; Array[a, 105] (* Robert G. Wilson v, Dec 09 2005 *)
(* Alternative: *)
Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* Peter Luschny, Dec 02 2017 *)
(* Alternative: *)
a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* Michael Somos, Jul 10 2018 *)
(* Alternative: *)
Join[{0}, IntegerLength[Range[130], 2]] (* Vincenzo Librandi, Jun 14 2019 *)
(* Alternative: *)
Ceiling[Log2[Range[20]]] (* Eric W. Weisstein, Jun 29 2026 *)
PROG
(PARI) {a(n) = if( n<1, 0, ceil(log(n) / log(2)))};
(PARI) /* Set p = 1, then: */
xpcount(n, p) = for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0, p1/=2; ct++, p1 = p1*p+1)); print1(ct, ", "))
(PARI) {a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */
(Haskell)
a029837 n = a029837_list !! (n-1)
a029837_list = scanl1 (+) a209229_list
-- Reinhard Zumkeller, Mar 07 2012
(Common Lisp) (defun A029837 (n) (integer-length (1- n))) ; James Spahlinger, Oct 15 2012
(Magma) [Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019
(Scala) (1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020
(Python)
def A029837(n):
s = bin(n)[2:]
return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020
(Python)
def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022
CROSSREFS
Partial sums of A036987.
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Additional comments from Daniele Parisse
More terms from Michael Somos, Aug 02 2002
STATUS
approved