|
| |
|
|
A000523
|
|
Log_2(n) rounded down.
|
|
98
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| Or, n-1 appears 2^(n-1) times. - Jon Perry (perry(AT)globalnet.co.uk), 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 (reinhard.zumkeller(AT)gmail.com), 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 (reinhard.zumkeller(AT)gmail.com), May 20 2005
a(n) = A152487(n-1,0) = A152487(n,1). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 06 2008]
Contribution from Paul Weisenhorn (weisenhorn-f.p(AT)online.de), 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
|
|
|
REFERENCES
| R. Baumann, Computer-Knobelei, LOG IN Heft 159 (2009), 74-77 [From Paul Weisenhorn (weisenhorn-f.p(AT)online.de), 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.
|
|
|
LINKS
| N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Guo-Niu Han, Enumeration of Standard Puzzles
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 (reinhard.zumkeller(AT)gmail.com), Oct 29 2001
G.f.: 1/(1-x) * Sum(k>=1, x^2^k). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 13 2002
a(n)=k with 2^k <= n < 2^(k+1); a(n)=floor(lb(n)). - Paul Weisenhorn (weisenhorn-f.p(AT)online.de), 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 (weisenhorn-f.p(AT)online.de), 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 (weisenhorn-f.p(AT)online.de), Sep 29 2010
|
|
|
PROG
| (MAGMA) [Ilog2(n) : n in [1..130] ];
(PARI) a(n)=if(n<1, 0, floor(log(n)/log(2)))
(Haskell)
a000523 1 = 0
a000523 n = 1 + a000523 (div n 2)
-- Reinhard Zumkeller, 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,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
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
|
| |
|
|
