A070939 Length of binary representation of n.

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, 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, 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

Offset

0,3

Comments

Zero is assumed to be represented as 0.

For n>1, n appears 2^(n-1) times. - Lekraj Beedassy, Apr 12 2006

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

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

A103586(n) = a(n + a(n)); a(A214489(n)) = A103586(A214489(n)). - Reinhard Zumkeller, Jul 21 2012

Number of divisors of 2^n that are <= n. - Clark Kimberling, Apr 21 2019

References

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

Links

T. D. Noe, Table of n, a(n) for n = 0..1024

K. Hessami Pilehrood, and T. Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, 13 (2010), #10.7.3.

L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.

Ralf Stephan, Some divide-and-conquer sequences ...

Ralf Stephan, Table of generating functions

Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

Index entries for "core" sequences

Index entries for sequences related to binary expansion of n

Formula

a(0) = 1; for n >= 1, a(n) = 1 + floor(log_2(n)) = 1 + A000523(n).

G.f.: 1 + 1/(1-x) * Sum(k>=0, x^2^k). - Ralf Stephan, Apr 12 2002

a(0)=1, a(1)=1 and a(n) = 1+a(floor(n/2)). - Benoit Cloitre, Dec 02 2003

a(n) = A000120(n) + A023416(n). - Lekraj Beedassy, Apr 12 2006

a(2^m + k) = m + 1, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Mar 14 2017

a(n) = A113473(n) if n>0.

Example

8 = 1000 in binary has length 4.

Maple

A070939 := n -> `if`(n=0, 1, ilog2(2*n)):
seq(A070939(n), n=0..104); # revised by Peter Luschny, Aug 10 2017

Mathematica

Table[Length[IntegerDigits[n, 2]], {n, 0, 50}] (* Stefan Steinerberger, Apr 01 2006 *)
Join[{1}, IntegerLength[Range[110], 2]] (* Harvey P. Dale, Aug 18 2013 *)
a[ n_] := If[ n < 1, Boole[n == 0], BitLength[n]]; (* Michael Somos, Jul 10 2018 *)

Prog

(Magma) A070939:=func< n | n eq 0 select 1 else #Intseq(n, 2) >; [ A070939(n): n in [0..104] ]; // Klaus Brockhaus, Jan 13 2011
(PARI) {a(n) = if( n<1, n==0, #binary(n))} /* Michael Somos, Aug 31 2012 */
(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
(Haskell)
a070939 n = if n < 2 then 1 else a070939 (n `div` 2) + 1
a070939_list = 1 : 1 : l [1] where
   l bs = bs' ++ l bs' where bs' = map (+ 1) (bs ++ bs)
-- Reinhard Zumkeller, Jul 19 2012, Jun 07 2011
(Sage)
def A070939(n) : return (2*n).exact_log(2) if n != 0 else 1
[A070939(n) for n in range(100)] # Peter Luschny, Aug 08 2012
(Python)
def a(n): return len(bin(n)[2:])
print([a(n) for n in range(105)]) # Michael S. Branicky, Jan 01 2021
(Python)
def A070939(n): return 1 if n == 0 else n.bit_length() # Chai Wah Wu, May 12 2022

Crossrefs

Cf. A070940, A070941, A001511, A000523.

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).

This is Guy Steele's sequence GS(4, 4) (see A135416).

Cf. A000120, A007088, A023416, A059015, A113473.

Cf. A083652 (partial sums).

Sequence in context: A237261 A004258 A029837 * A113473 A265370 A356895

Adjacent sequences: A070936 A070937 A070938 * A070940 A070941 A070942

Keyword

nonn,easy,nice,core

Author

N. J. A. Sloane, May 18 2002

Extensions

a(4) corrected by Antti Karttunen, Feb 28 2003

Status

approved