|
%I M2407 #48 Nov 04 2022 07:30:51
%S 0,0,1,3,5,7,10,13,16,19,22,26,29,33,37,41,45,49,53,57,62,66,70,75,80,
%T 84,89,94,98,103,108,113,118,123,128,133,139,144,149,154,160,165,170,
%U 176,181,187,192,198,203,209,215,220,226,232,238,243,249,255,261,267
%N a(n) = ceiling(log_2 n!).
%C a(n) is a lower bound for the minimum number of comparisons needed to sort n elements using a comparison sort (A036604). - _Alex Costea_, Mar 23 2019
%D D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
%D E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4.
%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 Alois P. Heinz, <a href="/A003070/b003070.txt">Table of n, a(n) for n = 0..10000</a>
%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%t Array[Ceiling@ Log2[#!] &, 60, 0] (* _Michael De Vlieger_, Mar 27 2019 *)
%o (Magma) [Ceiling(Log(2,Factorial(n))) : n in [0..70]]; // _G. C. Greubel_, Nov 03 2022
%o (SageMath) [ceil(log(factorial(n),2)) for n in range(71)] # _G. C. Greubel_, Nov 03 2022
%Y Cf. A036604. Essentially the same as A072831.
%K nonn
%O 0,4
%A _N. J. A. Sloane_
|
