login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003070 a(n) = ceiling(log_2 n!).
(Formerly M2407)
13

%I M2407

%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 *)

%Y Cf. A036604. Essentially the same as A072831.

%K nonn

%O 0,4

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 06:54 EDT 2019. Contains 328315 sequences. (Running on oeis4.)