cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

This page as a plain text file.
%I A117627 #32 Jun 21 2017 18:49:29
%S A117627 0,2,16,112,832,6896,62368,619904,6733312,79268096,1010644736,
%T A117627 13833177088,203128772608,3175336112128,52723300200448,
%U A117627 927263962759168,17221421451378688,336720980854571008,6911300635636400128,148661140496700932096
%N A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).
%C A117627 Sorting methods have been constructed such that the lower bound of f(n) is achieved for n=1, 2, 3, 4, 5, 6, 9 and 10. Y. Césari was the first to show that f(7) is not obtainable. He also constructed optimal solutions for n=9 and 10. L. Kollár showed that the minimum number of comparisons needed for n=7 is 62416. - _Dmitry Kamenetsky_, Jun 11 2015
%D A117627 Y. Césari, Questionnaire codage et tris, PhD Thesis, University of Paris, 1968.
%D A117627 D. E. Knuth, TAOCP, Vol. 3, Section 5.3.1.
%H A117627 Alois P. Heinz, <a href="/A117627/b117627.txt">Table of n, a(n) for n = 1..450</a>
%H A117627 L. Kollár, <a href="http://dx.doi.org/10.1007/BFb0016270">Optimal sorting of seven element sets</a>, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, 449-457.
%H A117627 <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F A117627 Knuth gives an explicit formula.
%F A117627 a(n) = (q(n)+1)*n! - 2^q(n) with q(n) = A003070(n).
%p A117627 q:= n-> ceil(log[2](n!)):
%p A117627 a:= n-> (q(n)+1)*n! - 2^q(n):
%p A117627 seq(a(n), n=1..30);  # _Alois P. Heinz_, Jun 11 2015
%t A117627 q[n_] := Log[2, n!] // Ceiling; a[n_] := (q[n]+1)*n! - 2^q[n]; Array[a, 20] (* _Jean-François Alcover_, Feb 13 2016 *)
%o A117627 (PARI) a(n) = { my(N=n!, q = ceil(log(N)/log(2))); return ((q+1)*N - 2^q);} \\ _Michel Marcus_, Apr 21 2013
%Y A117627 Cf. A003070, A036604, A117628.
%K A117627 nonn
%O A117627 1,2
%A A117627 _N. J. A. Sloane_, Oct 06 2006