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