|
%I M2433 N0963 #113 Mar 30 2023 01:49:14
%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 T. D. Noe, <a href="/A001855/b001855.txt">Table of n, a(n) for n = 1..1000</a>
%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 *)
%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.
%K nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_
%E Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)
|
