A003070 a(n) = ceiling(log_2 n!).

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, 84, 89, 94, 98, 103, 108, 113, 118, 123, 128, 133, 139, 144, 149, 154, 160, 165, 170, 176, 181, 187, 192, 198, 203, 209, 215, 220, 226, 232, 238, 243, 249, 255, 261, 267

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

References

• D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
• E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to sorting

Crossrefs

Cf. A036604. Essentially the same as A072831.

Programs

Magma

[Ceiling(Log(2,Factorial(n))) : n in [0..70]]; // G. C. Greubel, Nov 03 2022

Mathematica

Array[Ceiling@ Log2[#!] &, 60, 0] (* Michael De Vlieger, Mar 27 2019 *)

SageMath

[ceil(log(factorial(n),2)) for n in range(71)] # G. C. Greubel, Nov 03 2022