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

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,4

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

Mathematica

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

Prog

(Magma) [Ceiling(Log(2, Factorial(n))) : n in [0..70]]; // G. C. Greubel, Nov 03 2022
(SageMath) [ceil(log(factorial(n), 2)) for n in range(71)] # G. C. Greubel, Nov 03 2022

Crossrefs

Cf. A036604. Essentially the same as A072831.

Sequence in context: A092757 A062430 A016040 * A036604 A001768 A327672

Adjacent sequences: A003067 A003068 A003069 * A003071 A003072 A003073

Keyword

nonn

Author

N. J. A. Sloane

Status

approved