|
| |
|
|
A000523
|
|
a(n) = floor(log_2(n)).
|
|
257
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
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
|
|
|
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.
|
|
|
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
|
|
|
EXAMPLE
|
a(5)=2 because the binary expansion of 5 (=101) has three bits.
|
|
|
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 *)
|
|
|
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 */
(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
(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
(Python)
def A000523(n):
return len(bin(n))-3 # Chai Wah Wu, Jul 09 2020
|
|
|
CROSSREFS
|
Cf. A000193, A000195, A001222, A001620, A003462, A004233, A029837, A032924, A061168 (partial sums), A070939, A081604, A107680, A113473, A152487, A240857.
Sequence in context: A345376 A029835 A074280 * A124156 A324965 A072749
Adjacent sequences: A000520 A000521 A000522 * A000524 A000525 A000526
|
|
|
KEYWORD
|
nonn,easy,nice,look
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
