login
a(n) = ceiling(log_2 n!).
(Formerly M2407)
13

%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_