A000523 - OEIS (original) (raw)

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

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

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

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

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) = k with 2^k <= n < 2^(k+1); a(n) = floor(log_2(n)). - Paul Weisenhorn, Sep 29 2010

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

EXAMPLE

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

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

PROG

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

(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 */

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

(Python)

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

(Python)

def a(n): return n.bit_length() - 1

CROSSREFS

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

EXTENSIONS

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