|
| |
|
|
A029837
|
|
Binary order of n: log_2(n) rounded up to next integer.
|
|
81
| |
|
|
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 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, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Or, ceiling(log_2(n)).
Worst case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n-1 (n>=2), which is also A070939(n-1).
Let x(0)=n>1 and x(k+1)=x(k)-floor(x(k)/2), then a(n) is the smallest integer such that x(a(n))=1. Benoit Cloitre, Aug 29, 2002.
Also number of division steps when go from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard (hillcino368(AT)gmail.com), Mar 25 2003
Number of ways to write n as (x+2^y), x>=0. Number of ways to write n+1 as 2^x+3^y (cf. A004050). - Benoit Cloitre (benoit7848c(AT)orange.fr), Mar 29 2003
The minimum number of cuts for dividing an object into n (possibly unequal) pieces. [From Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010]
|
|
|
REFERENCES
| R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..10000
Cino Hilliard, The x+1 conjecture
L. Levine, Fractal sequences and restricted Nim
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to binary expansion of n
|
|
|
FORMULA
| Ceiling( log_2 n ).
a(1) = 0; for n>1, a(2n) = a(n)+1, a(2n+1) = a(n)+1. Alternatively, a(1) = 0; for n>1, a(n) = a(floor(n/2))+1.
a(n) = k such that n^(1/k-1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k-1) < n < 2^k. - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), May 06 2001
G.f.: x/(1-x) * Sum(k>=0, x^2^k). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 13 2002
a(n+1)=-sum(k=1..n,mu(2k)floor(n/k)) [From Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 21 2009]
|
|
|
EXAMPLE
| a(1) = 0, since log_2(1) = 0. a(2) = 1, since log_2(2) = 1. a(3) = 2, since log_2(3) = 1.58... If a(n)=7, then n=65, 66, ..., 127, 128.
|
|
|
MATHEMATICA
| f[n_] := Ceiling[Log[2, n]]; Array[f, 105] (from Robert G. Wilson v (rgwv(at)rgwv.com), Dec 09 2005)
|
|
|
PROG
| (PARI) a(n)=if(n<1, 0, ceil(log(n)/log(2)))
(PARI) (Set p = 1, then:) xpcount(n, p) = { for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0, p1/=2; ct++, p1 = p1*p+1; ) ); print1(ct" ") ) }
|
|
|
CROSSREFS
| Cf. A000523, A070939, A000193, A000195, A004233.
Used for several definitions: A029827, A036378-A036390. Partial sums: A001855.
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Jul 06 2009: (Start)
A062383(n-1) = 2^a(n)
(End)
Sequence in context: A075172 A004258 * A070939 A113473 A196050 A122027
Adjacent sequences: A029834 A029835 A029836 * A029838 A029839 A029840
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional comments from Daniele Parisse (daniele.parisse(AT)m.dasa.de)
More terms from Michael Somos, Aug 02, 2002
|
| |
|
|
