login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000523 Log_2(n) rounded down. 129
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-1 appears 2^(n-1) 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(Omega(k): 1<=k<=n), where Omega(n)=A001222(n), number of prime factors with repetition; see A080613. - Reinhard Zumkeller, Feb 25 2003

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

From Paul Weisenhorn, Sep 29 2010: (Start)

Arithmetic mean: m(1,c/(c-1))=(2c+1)/2c; harmonic mean: h(1,c/(c-1))=2c/(2c-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. (End)

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) = Max{A240857(n,k): k = 1..n}. - Reinhard Zumkeller, Apr 14 2014

REFERENCES

R. Baumann, Computer-Knobelei, LOG IN Heft 159 (2009), 74-77 [From Paul Weisenhorn, Sep 29 2010]

G. H. Hardy, Note on Dr. Vacca's series..., Quart. J. Pure Appl. Math. 43 (1912) 215-216.

D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, p. 400.

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

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

FORMULA

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(lb(n)). - Paul Weisenhorn, Sep 29 2010

EXAMPLE

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

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; - Paul Weisenhorn, Sep 29 2010

MAPLE

A000523 := n->floor(simplify(log(n)/log(2)));

A000523 := proc(n) local nn, i; if(0 = n) then RETURN(-infinity); fi; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;

for n from 1 to 1000 do a[n]:=floor(log[2](n)); end do; - Paul Weisenhorn, Sep 29 2010

MATHEMATICA

Floor[Log[2, Range[110]]] (* Harvey P. Dale, Jul 16 2012 *)

PROG

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

(PARI) {a(n) = if( n<1, 0, floor(log(n) / log(2)))};

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

-- Reinhard Zumkeller, Dec 31 2012, Feb 04 2012, Mar 18 2011

CROSSREFS

Cf. A029837. Partial sums: A061168.

Cf. A000195, A000193, A004233.

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

Sequence in context: A186437 A029835 A074280 * A124156 A072749 A066490

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 18 22:41 EDT 2014. Contains 246937 sequences.