|
Search: id:A029837
|
|
|
| A029837 |
|
Binary order of n: log_2(n) rounded up to next integer. |
|
+0
69
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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
|
|
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
|
|
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)
|
|
PROGRAM
|
(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.
Sequence in context: A071673 A072660 A075172 this_sequence A070939 A113473 A122027
Adjacent sequences: A029834 A029835 A029836 this_sequence A029838 A029839 A029840
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
Additional comments from Daniele Parisse (daniele.parisse(AT)m.dasa.de)
More terms from Michael Somos, Aug 02, 2002
|
|
|
Search completed in 0.003 seconds
|
