|
%I #194 Apr 18 2023 14:45:46
%S 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,
%T 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,
%U 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
%N a(n) = floor(log_2(n)).
%C Or, n >= 0 appears 2^n times. - _Jon Perry_, Sep 21 2002
%C a(n) + 1 = number of bits in binary expansion of n.
%C Largest power of 2 dividing lcm(1..n): A007814(A003418(n)).
%C log_2(0) = -infinity.
%C 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
%C From _Paul Weisenhorn_, Sep 29 2010, updated Aug 11 2020: (Start)
%C 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);
%C 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.
%C 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.
%C The 4 twofold means for n from 4 to 7:
%C m(1,m(1,2)) = m(1,3/2) = 5/4,
%C h(1,m(1,2)) = h(1,3/2) = 6/5,
%C m(1,h(1,2)) = m(1,4/3) = 7/6,
%C h(1,h(1,2)) = h(1,4/3) = 8/7. (End) [Edited by _Petros Hadjicostas_, Jul 23 2020]
%C 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
%C 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
%C Number of powers of 2 <= n. - _Ralph-Joseph Tatt_, Apr 23 2018
%C 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
%C Minimum height of an n-node binary tree. - _Yuchun Ji_, Mar 22 2021
%D Rüdeger Baumann, Computer-Knobelei, LOG IN Heft 159 (2009), 74-77. - _Paul Weisenhorn_, Sep 29 2010
%D G. H. Hardy, Note on Dr. Vacca's series for gamma, Quart. J. Pure Appl. Math., Vol. 43 (1912), pp. 215-216.
%D Ernst Jacobsthal, Über die Eulersche konstante, Mathematisch-Naturwissenschaftliche Blätter, Vol. 3, No. 9 (1906), pp. 153-154.
%D Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, p. 400.
%D 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
%H N. J. A. Sloane, <a href="/A000523/b000523.txt">Table of n, a(n) for n = 1..10000</a>
%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]
%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.
%H G. H. Hardy, <a href="https://babel.hathitrust.org/cgi/pt?id=inu.30000050138266&view=1up&seq=225">Note on Dr. Vacca's series for gamma</a>, Quart. J. Pure Appl. Math. 43 (1912), 215-216. [Available only in the USA through the <a href="https://www.hathitrust.org/">Hathi Trust</a>.]
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions (ps file)</a>.
%H Ralf Stephan, <a href="/A000523/a000523.pdf">Table of generating functions (pdf file)</a>.
%H G. Vacca, <a href="https://books.google.fr/books?id=Q4qXAAAAMAAJ&hl=fr&pg=PA363#v=onepage&q&f=false">A new series for the Eulerian constant gamma=.577...</a>, Quart. J. Pure Appl. Math., Vol. 41 (1910), pp. 363-368.
%F a(n) = A070939(n) - 1 for n >= 1.
%F a(n) = if n > 1, then a(floor(n / 2)) + 1; else 0. - _Reinhard Zumkeller_, Oct 29 2001
%F G.f.: (1/(1 - x)) * Sum_{k>=1} x^2^k. - _Ralf Stephan_, Apr 13 2002
%F 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
%F a(n) = A152487(n-1,0) = A152487(n,1). - _Reinhard Zumkeller_, Dec 06 2008
%F a(n) = k with 2^k <= n < 2^(k+1); a(n) = floor(log_2(n)). - _Paul Weisenhorn_, Sep 29 2010
%F a(n) = Max_{k=1..n} A240857(n,k). - _Reinhard Zumkeller_, Apr 14 2014
%F a(n) = A113473(n) - 1. - _Filip Zaludek_, Oct 29 2016
%F Sum_{n>=2} (-1)^n*a(n)/n = gamma = A001620 (Jacobsthal, 1906; Vacca, 1910). - _Amiram Eldar_, Jun 12 2021
%e a(5)=2 because the binary expansion of 5 (=101) has three bits.
%p A000523 := proc(n)
%p ilog2(n) ;
%p end proc: # _R. J. Mathar_, Nov 28 2016
%p seq(A000523(n), n=1..90);
%t Floor[Log[2,Range[110]]] (* _Harvey P. Dale_, Jul 16 2012 *)
%t a[ n_] := If[ n < 1, 0, BitLength[n] - 1]; (* _Michael Somos_, Jul 10 2018 *)
%o (Magma) [Ilog2(n) : n in [1..130] ];
%o (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.
%o (PARI) {a(n) = if( n<1, 0, #binary(n) - 1)}; /* _Michael Somos_, May 28 2014 */
%o (PARI) a(n)=logint(n,2) \\ _Charles R Greathouse IV_, Sep 01 2015
%o (PARI) a(n)=exponent(n) \\ _Charles R Greathouse IV_, Nov 09 2017
%o (Haskell)
%o a000523 1 = 0
%o a000523 n = 1 + a000523 (div n 2)
%o a000523_list = 0 : f [0] where
%o f xs = ys ++ f ys where ys = map (+ 1) (xs ++ xs)
%o -- _Reinhard Zumkeller_, Dec 31 2012, Feb 04 2012, Mar 18 2011
%o (Python)
%o def A000523(n):
%o return len(bin(n))-3 # _Chai Wah Wu_, Jul 09 2020
%o (Python)
%o def a(n): return n.bit_length() - 1
%o print([a(n) for n in range(1, 106)]) # _Michael S. Branicky_, Apr 18 2023
%Y Cf. A000193, A000195, A001222, A001620, A003462, A004233, A029837, A032924, A061168 (partial sums), A070939, A081604, A107680, A113473, A152487, A240857.
%K nonn,easy,nice,look
%O 1,4
%A _N. J. A. Sloane_
%E Error in 4th term, pointed out by Joe Keane (jgk(AT)jgk.org), has been corrected.
%E More terms from _Michael Somos_, Aug 02 2002
|
