cp's OEIS Frontend

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

%I A001855 M2433 N0963 #124 Feb 16 2025 08:32:24
%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,
%T A001855 94,99,104,109,114,119,124,129,135,141,147,153,159,165,171,177,183,
%U A001855 189,195,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_, Dec 05 2006
%C A001855 It is also coincidentally the maximum number of comparisons for merge sort. - _Li-yao Xia_, Nov 18 2015
%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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001855 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%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 Paolo Xausa, <a href="/A001855/b001855.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%H A001855 Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, <a href="https://arxiv.org/abs/1710.04240">Universal layered permutations</a>, arXiv:1710.04240 [math.CO], (2017).
%H A001855 Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, <a href="https://doi.org/10.37236/7386">Universal Layered Permutations</a>, Electronic Journal of Combinatorics. Volume 25(3), 2018, #P3.23.
%H A001855 J.-P. Allouche and J. Shallit, <a href="https://doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.
%H A001855 Sung-Hyuk Cha, <a href="http://www.wseas.us/e-library/conferences/2012/CambridgeUSA/MATHCC/MATHCC-60.pdf">On Integer Sequences Derived from Balanced k-ary Trees</a>, Applied Mathematics in Electrical and Computer Engineering, 2012.
%H A001855 Sung-Hyuk Cha, <a href="http://naun.org/multimedia/UPress/ami/16-125.pdf">On Complete and Size Balanced k-ary Tree Integer Sequences</a>, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
%H A001855 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A001855 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A001855 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 36.
%H A001855 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H A001855 D. Knuth, <a href="/A003063/a003063.pdf">Letter to N. J. A. Sloane, date unknown</a>
%H A001855 N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 5.
%H A001855 R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A001855 R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H A001855 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Sorting.html">Sorting</a>.
%H A001855 <a href="/index/So#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_, 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_, Apr 13 2002
%F A001855 a(1)=0, for n>1, a(n) = ceiling(n*a(n-1)/(n-1)+1). - _Benoit Cloitre_, Apr 26 2003
%F A001855 a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - _Vladeta Jovovic_, Aug 15 2004
%F A001855 a(n) = A061168(n-1) + n - 1 for n>1. - _Hieronymus Fischer_, Dec 05 2006
%F A001855 a(n) = A123753(n-1) - n. - _Peter Luschny_, Nov 30 2017
%p A001855 a := proc(n) local k; k := ilog2(n) + 1; 1 + n*k - 2^k end; # _N. J. A. Sloane_, Dec 01 2007 [edited by _Peter Luschny_, Nov 30 2017]
%t A001855 a[n_?EvenQ] := a[n] = n + 2a[n/2] - 1; a[n_?OddQ] := a[n] = n + a[(n+1)/2] + a[(n-1)/2] - 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 58}] (* _Jean-François Alcover_, Nov 23 2011, after Pari *)
%t A001855 a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + 1;
%t A001855 Table[a[n], {n, 1, 58}] (* _Peter Luschny_, Dec 02 2017 *)
%t A001855 Accumulate[BitLength[Range[0, 100]]] (* _Paolo Xausa_, Sep 30 2024 *)
%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)
%o A001855 (Haskell)
%o A001855 import Data.List (transpose)
%o A001855 a001855 n = a001855_list !! n
%o A001855 a001855_list = 0 : zipWith (+) [1..] (zipWith (+) hs $ tail hs) where
%o A001855    hs = concat $ transpose [a001855_list, a001855_list]
%o A001855 -- _Reinhard Zumkeller_, Jun 03 2013
%o A001855 (Python)
%o A001855 def A001855(n):
%o A001855     s, i, z = 0, n-1, 1
%o A001855     while 0 <= i: s += i; i -= z; z += z
%o A001855     return s
%o A001855 print([A001855(n) for n in range(1, 59)]) # _Peter Luschny_, Nov 30 2017
%o A001855 (Python)
%o A001855 def A001855(n): return n*(m:=(n-1).bit_length())-(1<<m)+1 # _Chai Wah Wu_, Mar 29 2023
%Y A001855 Partial sums of A029837.
%Y A001855 Cf. A003071, A000337, A030190, A030308, A061168, A123753, A373709.
%K A001855 nonn,easy,nice
%O A001855 1,3
%A A001855 _N. J. A. Sloane_
%E A001855 Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)