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
Examples
8 = 1000 in binary has length 4.
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
Crossrefs
Programs
-
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
-
Magma
A070939:=func< n | n eq 0 select 1 else #Intseq(n, 2) >; [ A070939(n): n in [0..104] ]; // Klaus Brockhaus, Jan 13 2011
-
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 *) -
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 -
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
-
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
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(2^m + k) = m + 1, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Mar 14 2017
a(n) = A113473(n) if n>0.
Extensions
a(4) corrected by Antti Karttunen, Feb 28 2003
Comments