Search: id:A001855
Results 1-1 of 1 results found.

%I A001855 M2433 N0963
%S A001855 0,1,3,5,8,11,14,17,21,25,29,33,37,41,45,49,54,59,64,69,74,79,84,89,94,
%T A001855 99,104,109,114,119,124,129,135,141,147,153,159,165,171,177,183,189,195,
%U A001855 201,207,213,219,225,231,237,243,249,255,261,267,273,279,285
%N A001855 Sorting numbers: maximal number of comparisons for sorting n elements 
               by binary insertion.
%C A001855 Equals n-1 times the expected number of probes for a successful binary 
               search in a size n-1 list.
%C A001855 Piecewise linear: breakpoints at powers of 2 with values given by A000337.
%C A001855 a(n) is the number of digits in the binary representation of all the 
               numbers 1 to n-1. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Dec 05 2006
%D A001855 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A001855 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A001855 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical 
               Computer Sci., 98 (1992), 163-197.
%D A001855 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, 
               MA, Vol. 3, Sect 5.3.1, Eq. (3); Sect. 6.2.1 (4).
%D A001855 J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.
%D A001855 Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, 
               Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.
%H A001855 T. D. Noe, <a href="b001855.txt">Table of n, a(n) for n=1..1000</a>
%H A001855 J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/
               Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer 
               Sci., 98 (1992), 163-197.
%H A001855 R. Stephan, <a href="somedcgf.html">Some divide-and-conquer sequences 
               ...</a>
%H A001855 R. Stephan, <a href="a079944.ps">Table of generating functions</a>
%H A001855 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Sorting.html">Link to a section of The World of Mathematics.</a>
%H A001855 <a href="Sindx_So.html#sorting">Index entries for sequences related to 
               sorting</a>
%F A001855 Let n = 2^(k-1) + g, 0 <= g < 2^(k-1); then a(n) = 1 + n*k - 2^k. - N. 
               J. A. Sloane (njas(AT)research.att.com), Dec 01 2007
%F A001855 a(n) = Sum_{k=1..n} ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) 
               + 1.
%F A001855 a(n)=a(floor(n/2))+a(ceiling(n/2))+n-1.
%F A001855 G.f.: x/(1-x)^2 * Sum(k>=0, x^2^k). - Ralf Stephan (ralf(AT)ark.in-berlin.de), 
               Apr 13 2002
%F A001855 a(1)=0, for n>1, a(n)=ceiling(n*a(n-1)/(n-1)+1) - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Apr 26 2003
%F A001855 a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - Vladeta 
               Jovovic (vladeta(AT)eunet.rs), Aug 15 2004
%F A001855 a(n) = A061168(n-1)+n-1 for n>1 - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Dec 05 2006
%p A001855 Digits:=200; f:=proc(n) local k,x; x:=floor(log(n)/log(2)); k:=x+1; 1+n*k-2^k; 
               end; - N. J. A. Sloane (njas(AT)research.att.com), Dec 01 2007
%o A001855 (PARI) a(n)=if(n<2,0,n-1+a(n\2)+a((n+1)\2))
%o A001855 (PARI) a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+1)
%Y A001855 Partial sums of A029837.
%Y A001855 Cf. A003071, A000337, A030190, A030308, A061168.
%Y A001855 Cf. A061168.
%Y A001855 Sequence in context: A102696 A130262 A094228 this_sequence A006591 A052488 
               A076372
%Y A001855 Adjacent sequences: A001852 A001853 A001854 this_sequence A001856 A001857 
               A001858
%K A001855 nonn,easy,nice
%O A001855 1,3
%A A001855 N. J. A. Sloane (njas(AT)research.att.com).
%E A001855 Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu).

Search completed in 0.002 seconds