login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A070939 Length of binary representation of n. 196
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 (list; graph; refs; listen; history; text; internal format)
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

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

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

R. Stephan, Table of generating functions

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences

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

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

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) A070939 = n->#binary(n)+!n \\ 25% faster than the preceding code. - M. F. Hasler, Jan 04 2014

(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

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.

Cf. A083652 (partial sums).

Sequence in context: A237261 A004258 A029837 * A113473 A265370 A238407

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 03:32 EDT 2017. Contains 292441 sequences.