%I #109 May 13 2022 05:49:43
%S 1,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 Length of binary representation of n.
%C Zero is assumed to be represented as 0.
%C For n>1, n appears 2^(n-1) times. - _Lekraj Beedassy_, Apr 12 2006
%C a(n) is the permanent of the n X n 0-1 matrix whose (i,j) entry is 1 iff i=1 or i=j or i=2*j. For example, a(4)=3 is per([[1, 1, 1, 1], [1, 1, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]). - _David Callan_, Jun 07 2006
%C a(n) is the number of different contiguous palindromic bit patterns in the binary representation of n; for examples, for 5=101_2 the bit patterns are 0, 1, 101; for 7=111_2 the corresponding patterns are 1, 11, 111; for 13=1101_2 the patterns are 0, 1, 11, 101. - _Hieronymus Fischer_, Mar 13 2012
%C A103586(n) = a(n + a(n)); a(A214489(n)) = A103586(A214489(n)). - _Reinhard Zumkeller_, Jul 21 2012
%C Number of divisors of 2^n that are <= n. - _Clark Kimberling_, Apr 21 2019
%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.
%H T. D. Noe, <a href="/A070939/b070939.txt">Table of n, a(n) for n = 0..1024</a>
%H K. Hessami Pilehrood, and T. Hessami Pilehrood, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Pilehrood/pilehrood2.html">Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative</a>, J. Integer Sequences, 13 (2010), #10.7.3.
%H L. Levine, <a href="https://arxiv.org/abs/math/0409408">Fractal sequences and restricted Nim</a>, arXiv:math/0409408 [math.CO], 2004.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F a(0) = 1; for n >= 1, a(n) = 1 + floor(log_2(n)) = 1 + A000523(n).
%F G.f.: 1 + 1/(1-x) * Sum(k>=0, x^2^k). - _Ralf Stephan_, Apr 12 2002
%F a(0)=1, a(1)=1 and a(n) = 1+a(floor(n/2)). - _Benoit Cloitre_, Dec 02 2003
%F a(n) = A000120(n) + A023416(n). - _Lekraj Beedassy_, Apr 12 2006
%F a(2^m + k) = m + 1, m >= 0, 0 <= k < 2^m. - _Yosu Yurramendi_, Mar 14 2017
%F a(n) = A113473(n) if n>0.
%e 8 = 1000 in binary has length 4.
%p A070939 := n -> `if`(n=0, 1, ilog2(2*n)):
%p seq(A070939(n), n=0..104); # revised by _Peter Luschny_, Aug 10 2017
%t Table[Length[IntegerDigits[n, 2]], {n, 0, 50}] (* _Stefan Steinerberger_, Apr 01 2006 *)
%t Join[{1},IntegerLength[Range[110],2]] (* _Harvey P. Dale_, Aug 18 2013 *)
%t a[ n_] := If[ n < 1, Boole[n == 0], BitLength[n]]; (* _Michael Somos_, Jul 10 2018 *)
%o (Magma) A070939:=func< n | n eq 0 select 1 else #Intseq(n, 2) >; [ A070939(n): n in [0..104] ]; // _Klaus Brockhaus_, Jan 13 2011
%o (PARI) {a(n) = if( n<1, n==0, #binary(n))} /* _Michael Somos_, Aug 31 2012 */
%o (PARI) apply( {A070939(n)=exponent(n+!n)+1}, [0..99]) \\ works for negative n and is much faster than the above. - _M. F. Hasler_, Jan 04 2014, updated Feb 29 2020
%o (Haskell)
%o a070939 n = if n < 2 then 1 else a070939 (n `div` 2) + 1
%o a070939_list = 1 : 1 : l [1] where
%o l bs = bs' ++ l bs' where bs' = map (+ 1) (bs ++ bs)
%o -- _Reinhard Zumkeller_, Jul 19 2012, Jun 07 2011
%o (Sage)
%o def A070939(n) : return (2*n).exact_log(2) if n != 0 else 1
%o [A070939(n) for n in range(100)] # _Peter Luschny_, Aug 08 2012
%o (Python)
%o def a(n): return len(bin(n)[2:])
%o print([a(n) for n in range(105)]) # _Michael S. Branicky_, Jan 01 2021
%o (Python)
%o def A070939(n): return 1 if n == 0 else n.bit_length() # _Chai Wah Wu_, May 12 2022
%Y Cf. A070940, A070941, A001511, A000523.
%Y A029837(n+1) gives the length of binary representation of n without the leading zeros (i.e., when zero is represented as the empty sequence). For n > 0 this is equal to a(n).
%Y This is Guy Steele's sequence GS(4, 4) (see A135416).
%Y Cf. A000120, A007088, A023416, A059015, A113473.
%Y Cf. A083652 (partial sums).
%K nonn,easy,nice,core
%O 0,3
%A _N. J. A. Sloane_, May 18 2002
%E a(4) corrected by _Antti Karttunen_, Feb 28 2003