A001855 - OEIS

%I M2433 N0963 #123 Sep 30 2024 16:54:15

%S 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 94,99,104,109,114,119,124,129,135,141,147,153,159,165,171,177,183,

%U 189,195,201,207,213,219,225,231,237,243,249,255,261,267,273,279,285

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

%C Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.

%C Piecewise linear: breakpoints at powers of 2 with values given by A000337.

%C 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 It is also coincidentally the maximum number of comparisons for merge sort. - _Li-yao Xia_, Nov 18 2015

%D 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 J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D 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 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 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 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 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 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 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 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 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 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 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.

%H D. Knuth, <a href="/A003063/a003063.pdf">Letter to N. J. A. Sloane, date unknown</a>

%H 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 R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Sorting.html">Sorting</a>.

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F 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 a(n) = Sum_{k=1..n}ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) + 1.

%F a(n) = a(floor(n/2)) + a(ceiling(n/2)) + n - 1.

%F G.f.: x/(1-x)^2 * Sum_{k>=0} x^2^k. - _Ralf Stephan_, Apr 13 2002

%F a(1)=0, for n>1, a(n) = ceiling(n*a(n-1)/(n-1)+1). - _Benoit Cloitre_, Apr 26 2003

%F a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - _Vladeta Jovovic_, Aug 15 2004

%F a(n) = A061168(n-1) + n - 1 for n>1. - _Hieronymus Fischer_, Dec 05 2006

%F a(n) = A123753(n-1) - n. - _Peter Luschny_, Nov 30 2017

%p 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 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 a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + 1;

%t Table[a[n], {n, 1, 58}] (* _Peter Luschny_, Dec 02 2017 *)

%t Accumulate[BitLength[Range[0, 100]]] (* _Paolo Xausa_, Sep 30 2024 *)

%o (PARI) a(n)=if(n<2,0,n-1+a(n\2)+a((n+1)\2))

%o (PARI) a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+1)

%o (Haskell)

%o import Data.List (transpose)

%o a001855 n = a001855_list !! n

%o a001855_list = 0 : zipWith (+) [1..] (zipWith (+) hs $ tail hs) where

%o    hs = concat $ transpose [a001855_list, a001855_list]

%o -- _Reinhard Zumkeller_, Jun 03 2013

%o (Python)

%o def A001855(n):

%o     s, i, z = 0, n-1, 1

%o     while 0 <= i: s += i; i -= z; z += z

%o     return s

%o print([A001855(n) for n in range(1, 59)]) # _Peter Luschny_, Nov 30 2017

%o (Python)

%o def A001855(n): return n*(m:=(n-1).bit_length())-(1<<m)+1 # _Chai Wah Wu_, Mar 29 2023

%Y Partial sums of A029837.

%Y Cf. A003071, A000337, A030190, A030308, A061168, A123753, A373709.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)