|
%I #95 Sep 06 2023 21:17:47
%S 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,
%T 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,
%U 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
%N Binary order of n: log_2(n) rounded up to next integer.
%C Or, ceiling(log_2(n)).
%C Worst-case cost of binary search.
%C Equal to number of binary digits in n unless n is a power of 2 when it is one less.
%C Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1).
%C 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
%C 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
%C 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
%C The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
%C Partial sums of A209229; number of powers of 2 not greater than n. - _Reinhard Zumkeller_, Mar 07 2012
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
%D G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.
%H T. D. Noe, <a href="/A029837/b029837.txt">Table of n, a(n) for n = 1..10000</a>
%H Cino Hilliard, <a href="http://groups.msn.com/BC2LCC/page.msnw?fc_p=%2Fkx%2Bp%20problems&fc_a=0">The x+1 conjecture</a> [broken link]
%H Lionel Levine, <a href="https://arxiv.org/abs/math/0409408">Fractal sequences and restricted Nim</a>, arXiv:math/0409408 [math.CO], 2004.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BitLength.html">Bit Length.</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F a(n) = ceiling(log_2(n)).
%F 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]
%F 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
%F G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - _Ralf Stephan_, Apr 13 2002
%F A062383(n-1) = 2^a(n). - _Johannes W. Meijer_, Jul 06 2009
%F a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - _Benoit Cloitre_, Oct 21 2009
%F a(n+1) = A113473(n). - _Michael Somos_, Jun 02 2019
%e a(1) = 0, since log_2(1) = 0.
%e a(2) = 1, since log_2(2) = 1.
%e a(3) = 2, since log_2(3) = 1.58...
%e a(n) = 7 for n = 65, 66, ..., 127, 128.
%e 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
%p a:= n-> (p-> p+`if`(2^p<n, 1, 0))(ilog2(n)):
%p seq(a(n), n=1..120); # _Alois P. Heinz_, Mar 18 2013
%t a[n_] := Ceiling[Log[2, n]]; Array[a, 105] (* _Robert G. Wilson v_, Dec 09 2005 *)
%t Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* _Peter Luschny_, Dec 02 2017 *)
%t a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* _Michael Somos_, Jul 10 2018 *)
%t Join[{0}, IntegerLength[Range[130], 2]] (* _Vincenzo Librandi_, Jun 14 2019 *)
%o (PARI) {a(n) = if( n<1, 0, ceil(log(n) / log(2)))};
%o (PARI) /* Set p = 1, then: */
%o 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, ", "))
%o (PARI) {a(n) = if( n<2, 0, exponent(n-1)+1)}; /* _Michael Somos_, Jul 10 2018 */
%o (Haskell)
%o a029837 n = a029837_list !! (n-1)
%o a029837_list = scanl1 (+) a209229_list
%o -- _Reinhard Zumkeller_, Mar 07 2012
%o (Common Lisp) (defun A029837 (n) (integer-length (1- n))) ; _James Spahlinger_, Oct 15 2012
%o (Magma) [Ceiling(Log(2, n)): n in [1..100]]; // _Vincenzo Librandi_, Jun 14 2019
%o (Scala) (1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // _Alonso del Arte_, Feb 19 2020
%o (Python)
%o def A029837(n):
%o s = bin(n)[2:]
%o return len(s) - (1 if s.count('1') == 1 else 0) # _Chai Wah Wu_, Jul 09 2020
%o (Python)
%o def A029837(n): return (n-1).bit_length() # _Chai Wah Wu_, Jun 30 2022
%Y Cf. A000523, A070939, A000193, A000195, A004233, A113473, A053644.
%Y Partial sums of A036987.
%Y Used for several definitions: A029827, A036378-A036390. Partial sums: A001855.
%K nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_
%E Additional comments from _Daniele Parisse_
%E More terms from _Michael Somos_, Aug 02 2002
|
