A000523 a(n) = floor(log_2(n)).

0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 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, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• look

Comments

Or, n >= 0 appears 2^n times. - Jon Perry, Sep 21 2002

a(n) + 1 = number of bits in binary expansion of n.

Largest power of 2 dividing lcm(1..n): A007814(A003418(n)).

log_2(0) = -infinity.

Also Max_{k=1..n} Omega(k), where Omega(n) = A001222(n), number of prime factors with repetition; see A080613. - Reinhard Zumkeller, Feb 25 2003

From Paul Weisenhorn, Sep 29 2010, updated Aug 11 2020: (Start)

Arithmetic mean: m(1,(c+1)/c) = (2*c+1)/(2*c); harmonic mean: h(1,(c+1)/c) = 2*(c+1)/(2*c+1);

a(n) is the number of means to reach (n+1)/n from 2/1; with m for 0 and h for 1, the inverse binary expansion of n, without the leading 1, gives the sequence of means.

For example, n=20; inverse binary expansion without the leading 1: 0010 ---> m m h m or m(1, m(1, h(1, m(1, 2)))) = 21/20.

The 4 twofold means for n from 4 to 7:

m(1,m(1,2)) = m(1,3/2) = 5/4,

h(1,m(1,2)) = h(1,3/2) = 6/5,

m(1,h(1,2)) = m(1,4/3) = 7/6,

h(1,h(1,2)) = h(1,4/3) = 8/7. (End) [Edited by Petros Hadjicostas, Jul 23 2020]

As function of the absolute value, defines the minimal Euclidean function v on Z\{0}. A ring R is Euclidean if for some function v : R\{0}->N a division by nonzero b can be defined with remainder r satisfying either r=0 or v(r) < v(b). For the integers taking v(n)=|n| works, but v(n) = floor(log_2(|n|)) works as well; moreover it is the possibility with smallest possible values. For division by b>0 one can always choose |r| <= floor(b/2); this sequence satisfies a(1) = 0 and recursively a(n) = 1 + max(a(1), ..., a(floor(n/2))) for n > 1. - Marc A. A. van Leeuwen, Feb 16 2011

Maximum number of guesses required to find any k in a range of 1..n, with 'higher', 'lower' and 'correct' as answers. - Jon Perry, Nov 02 2013

Number of powers of 2 <= n. - Ralph-Joseph Tatt, Apr 23 2018

a(n) + 1 is the minimum number of pairwise disjoint subsets of an n-element set such that for each k from 1 to n there is a set with cardinality k which is the union of some of those subsets. - Wojciech Raszka, Apr 15 2019

Minimum height of an n-node binary tree. - Yuchun Ji, Mar 22 2021

Examples

			a(5)=2 because the binary expansion of 5 (=101) has three bits.
		

References

• Rüdeger Baumann, Computer-Knobelei, LOG IN Heft 159 (2009), 74-77. - Paul Weisenhorn, Sep 29 2010
• G. H. Hardy, Note on Dr. Vacca's series for gamma, Quart. J. Pure Appl. Math., Vol. 43 (1912), pp. 215-216.
• Ernst Jacobsthal, Über die Eulersche konstante, Mathematisch-Naturwissenschaftliche Blätter, Vol. 3, No. 9 (1906), pp. 153-154.
• Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, p. 400.
• Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589. - From N. J. A. Sloane, Aug 03 2012

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..10000
• Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
• Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
• G. H. Hardy, Note on Dr. Vacca's series for gamma, Quart. J. Pure Appl. Math. 43 (1912), 215-216. [Available only in the USA through the Hathi Trust.]
• Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
• Ralf Stephan, Table of generating functions (ps file).
• Ralf Stephan, Table of generating functions (pdf file).
• G. Vacca, A new series for the Eulerian constant gamma=.577..., Quart. J. Pure Appl. Math., Vol. 41 (1910), pp. 363-368.

Crossrefs

Cf. A000193, A000195, A001222, A001620, A003462, A004233, A029837, A032924, A061168 (partial sums), A070939, A081604, A107680, A113473, A152487, A240857.

Programs

Haskell

a000523 1 = 0
a000523 n = 1 + a000523 (div n 2)
a000523_list = 0 : f [0] where
   f xs = ys ++ f ys where ys = map (+ 1) (xs ++ xs)
-- Reinhard Zumkeller, Dec 31 2012, Feb 04 2012, Mar 18 2011

Magma

[Ilog2(n) : n in [1..130] ];

Maple

A000523 := proc(n)
    ilog2(n) ;
end proc: # R. J. Mathar, Nov 28 2016
seq(A000523(n), n=1..90);

Mathematica

Floor[Log[2,Range[110]]] (* Harvey P. Dale, Jul 16 2012 *)
a[ n_] := If[ n < 1, 0, BitLength[n] - 1]; (* Michael Somos, Jul 10 2018 *)

PARI

{a(n) = floor(log(n) / log(2))} \\ Likely to yield incorrect results for many if not almost all n. Better use most recent code.

PARI

{a(n) = if( n<1, 0, #binary(n) - 1)}; /* Michael Somos, May 28 2014 */

PARI

a(n)=logint(n,2) \\ Charles R Greathouse IV, Sep 01 2015

PARI

a(n)=exponent(n) \\ Charles R Greathouse IV, Nov 09 2017

Python

def A000523(n):
    return len(bin(n))-3 # Chai Wah Wu, Jul 09 2020

Python

def a(n): return n.bit_length() - 1
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Apr 18 2023

Formula

a(n) = A070939(n) - 1 for n >= 1.

a(n) = if n > 1, then a(floor(n / 2)) + 1; else 0. - Reinhard Zumkeller, Oct 29 2001

G.f.: (1/(1 - x)) * Sum_{k>=1} x^2^k. - Ralf Stephan, Apr 13 2002

a(n+1) = number of digits of n-th number with no 0 in ternary representation = A081604(A032924(n)); A107680(n) = A003462(a(n+1)). - Reinhard Zumkeller, May 20 2005

a(n) = A152487(n-1,0) = A152487(n,1). - Reinhard Zumkeller, Dec 06 2008

a(n) = k with 2^k <= n < 2^(k+1); a(n) = floor(log_2(n)). - Paul Weisenhorn, Sep 29 2010

a(n) = Max_{k=1..n} A240857(n,k). - Reinhard Zumkeller, Apr 14 2014

a(n) = A113473(n) - 1. - Filip Zaludek, Oct 29 2016

Sum_{n>=2} (-1)^n*a(n)/n = gamma = A001620 (Jacobsthal, 1906; Vacca, 1910). - Amiram Eldar, Jun 12 2021

a(n) = floor(Sum_{k=1..n-1} (n+1)^(n-2^k)) mod n. - Joseph M. Shunia, Jul 19 2024

Extensions

Error in 4th term, pointed out by Joe Keane (jgk(AT)jgk.org), has been corrected.

More terms from Michael Somos, Aug 02 2002