A003070 -id:A003070 - cp's OEIS frontend

A067850 Highest power of 2 not exceeding n!.

0, 0, 1, 2, 4, 6, 9, 12, 15, 18, 21, 25, 28, 32, 36, 40, 44, 48, 52, 56, 61, 65, 69, 74, 79, 83, 88, 93, 97, 102, 107, 112, 117, 122, 127, 132, 138, 143, 148, 153, 159, 164, 169, 175, 180, 186, 191, 197, 202, 208, 214, 219, 225, 231, 237, 242, 248, 254, 260, 266

Offset: 0

Lekraj Beedassy, Feb 15 2002

nonn

2^a(n) <= n! < 2^[a(n)+1]

Amiram Eldar, Table of n, a(n) for n = 0..10000

Cf. A000142.

Cf. A003070 (minimum number of bits to represent n!)

[Floor(Log(2,Factorial(k))):k in [0..60]]; // Marius A. Burtea, Nov 06 2019

f[n_] := Block[{k = 0}, While[2^k <= n!, k++ ]; k--; k]; Table[ f[n], {n, 0, 60} ]

floor(log[2](n!)). - Vladeta Jovovic, Feb 18 2002

Edited and extended by Robert G. Wilson v, Feb 16 2002

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264

Offset: 0

Daniel Krenn, Jun 20 2017

The 3 pivot elements are chosen from fixed indices (e.g., the last 3 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.

a(9)-a(11) from Melanie Siebenhofer, Jan 29 2018

a(12)-a(13) from Melanie Siebenhofer, Feb 02 2018

A049775 a(n) is the sum of all integers from 2^(n-2)+1 to 2^(n-1).

Original entry on oeis.org

2, 7, 26, 100, 392, 1552, 6176, 24640, 98432, 393472, 1573376, 6292480, 25167872, 100667392, 402661376, 1610629120, 6442483712, 25769869312, 103079346176, 412317122560, 1649267965952, 6597070815232, 26388281163776

Offset: 2

Clark Kimberling

nonn

Name when submitted: Sum of even-indexed terms of n-th row of array T given by A049773 (from Clark Kimberling).
Also sum of integers of which the binary order [A029837] is n: a(n) = Sum_[x | ceiling(log_2(x)) = n ]. E.g., a(7) = 6176 = Apply[Plus, Table[w,{w,65,128}]].
This sequence may be obtained by filling a complete binary tree left-to-right, row by row with the integers onwards from 2 and then collecting the sums of the rows; e.g., 2, 3+4, 5+6+7+8, 9+10+11+12+13+14+15+16, etc. a(n) is then equal to the sum of row n-1. - Carl R. White, Aug 19 2003
If the offset is set to zero, the inverse binomial transform gives A007051 without its leading 1. - R. J. Mathar, Mar 26 2009

			a(2) = 2 = 2.
a(3) = 7 = 3 + 4.
a(4) =26 = 5 + 6 + 7 + 8.
..

Index entries for linear recurrences with constant coefficients, signature (6,-8).

Cf. A049773 (sequence motivating the original definition).
Cf. A049775(n+2) = A007582(n+1) - A007582(n).
Cf. A029837, A003070.

LinearRecurrence[{6,-8},{2,7},30] (* Harvey P. Dale, Mar 04 2013 *)

a(n) = 2^(n-3)*(3*2^(n-2)+1). - Carl R. White, Aug 19 2003
From Philippe Deléham, Feb 20 2004: (Start)
a(n+1) = 4*a(n) - 2^(n-2); see also A007582.
a(n+1) = 2^(n-2)*A004119(n). (End)
From R. J. Mathar, Mar 26 2009: (Start)
a(n) = 6*a(n-1) - 8*a(n-2).
G.f.: -x^2*(-2+5*x)/((4*x-1)*(2*x-1)). (End)

More terms from Michael Somos

Name change by Olivier Gérard, Oct 24 2017

A072831 Number of bits in n!.

Original entry on oeis.org

1, 1, 2, 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

Rick L. Shepherd, Jul 22 2002

			a(4)=5 because 4! = 4*3*2*1 = 24 (base 10) = 11000 (base 2), using 5 bits.

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

Cf. A034886 (decimal digits of n!), A000142 (n!). Essentially the same as A003070.

a:= n-> 1+ilog2(n!):
seq(a(n), n=0..100);  # Alois P. Heinz, May 03 2016

Floor[Log[2,Range[0,60]!]]+1 (* Harvey P. Dale, Nov 16 2011 *)

for(n=0,100,print1(floor(log(n!)/log(2))+1,","))

a(n) = #binary(n!); \\ Michel Marcus, Dec 23 2016

import math
def a(n):
  return len(bin(math.factorial(n))[2:]) # Indranil Ghosh, Dec 23 2016

a(n) = floor(log(n!)/log(2)) + 1.

A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

Original entry on oeis.org

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71

Offset: 1

N. J. A. Sloane

The Peczarski paper in Algorithmica has a table giving upper and lower bounds that differ by at most 1. In particular, the values a(20) = 62 and a(21) = 66 are also known. - Bodo Manthey, Mar 01 2007

D. E. Knuth, Art of Computer Programming, Vol. 3, 2nd. edition, Sect. 5.3.1.
E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4, p. 309.
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989. [Finds a(12).]

Eisa Alanazi, Malek Mouhoub, Sandra Zilles, Interactive Learning of Acyclic Conditional Preference Networks, arXiv:1801.03968 [cs.AI], 2018.
Enrico Iurlano and Günther R. Raidl, SAT-Based Search for Minwise Independent Families, arXiv:2412.11811 [cs.DM], 2024. See p. 5.
Marcin Peczarski, New Results in Minimum-Comparison Sorting, Algorithmica 40(2):133-145, 2004.
Marcin Peczarski, The Ford-Johnson algorithm still unbeaten for less than 47 elements, Information Processing Letters, Volume 101, Issue 3, 14 February 2007, Pages 126-128.
Marcin Peczarski, Towards optimal sorting of 16 elements, arXiv:1108.0866 [cs.DS], 2011.
Marcin Peczarski, Sorting 13 Elements Requires 34 Comparisons, Proc. of the 10th European Symp. on Algorithms (ESA), vol. 2452 of Lecture Notes in Comput. Sci., pp. 785-794. Springer, 2002.
Florian Stober and Armin Weiss, Lower bounds for sorting 16, 17, and 18 elements, 2023 Proc. Symp. Algorithm Engineering and Experiments pp. 201-213, 2023. SIAM; arXiv preprint, arXiv:2206.05597 [cs.DS], 2022.
Index entries for sequences related to sorting

A001768 is an upper bound, A003070 a lower bound.

Cf. A360495.

a(13) was determined by Marcin Peczarski. - Bodo Manthey, Sep 25 2002
a(14)=38 and a(22)=71 were determined by Marcin Peczarski. - Bodo Manthey (manthey(AT)cs.uni-sb.de), Feb 28 2007
a(16)=46, a(17)=50, and a(18)=54 were determined by Stober and Weiss. - Robert McLachlan, May 29 2024
a(19)-a(22) from table in arXiv preprint of Stober and Weiss. - Domotor Palvolgyi, Jun 03 2025

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

Original entry on oeis.org

0, 2, 16, 112, 832, 6896, 62368, 619904, 6733312, 79268096, 1010644736, 13833177088, 203128772608, 3175336112128, 52723300200448, 927263962759168, 17221421451378688, 336720980854571008, 6911300635636400128, 148661140496700932096

Offset: 1

N. J. A. Sloane, Oct 06 2006

nonn

Sorting methods have been constructed such that the lower bound of f(n) is achieved for n=1, 2, 3, 4, 5, 6, 9 and 10. Y. Césari was the first to show that f(7) is not obtainable. He also constructed optimal solutions for n=9 and 10. L. Kollár showed that the minimum number of comparisons needed for n=7 is 62416. - Dmitry Kamenetsky, Jun 11 2015

Y. Césari, Questionnaire codage et tris, PhD Thesis, University of Paris, 1968.
D. E. Knuth, TAOCP, Vol. 3, Section 5.3.1.

Alois P. Heinz, Table of n, a(n) for n = 1..450
L. Kollár, Optimal sorting of seven element sets, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, 449-457.
Index entries for sequences related to sorting

Cf. A003070, A036604, A117628.

q:= n-> ceil(log[2](n!)):
a:= n-> (q(n)+1)*n! - 2^q(n):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 11 2015

q[n_] := Log[2, n!] // Ceiling; a[n_] := (q[n]+1)*n! - 2^q[n]; Array[a, 20] (* Jean-François Alcover, Feb 13 2016 *)

a(n) = { my(N=n!, q = ceil(log(N)/log(2))); return ((q+1)*N - 2^q);} \\ Michel Marcus, Apr 21 2013

Knuth gives an explicit formula.

a(n) = (q(n)+1)*n! - 2^q(n) with q(n) = A003070(n).

A213857 Least m such that n! <= 3^m.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 8, 10, 12, 14, 16, 19, 21, 23, 26, 28, 31, 34, 36, 39, 42, 45, 47, 50, 53, 56, 59, 62, 65, 68, 72, 75, 78, 81, 84, 88, 91, 94, 98, 101, 104, 108, 111, 115, 118, 122, 125, 129, 132, 136, 139, 143, 146, 150, 154, 157, 161, 165, 168, 172, 176

Offset: 1

Clark Kimberling, Jul 17 2012

Also the number of digits in the ternary representation of n!. - Martin Renner, Jan 03 2022

			a(8) = 10 because 3^9 < 8! <= 3^10.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A003070, A072831, A213854.

seq(nops(convert(n!,base,3)),n=1..100); # Martin Renner, Jan 03 2022

Table[m=1; While[n!>3^m, m++]; m, {n,1,100}]

A061717 Binary order of n^n.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 29, 34, 39, 44, 49, 54, 59, 64, 70, 76, 81, 87, 93, 99, 105, 111, 117, 123, 129, 135, 141, 148, 154, 160, 167, 173, 180, 187, 193, 200, 207, 213, 220, 227, 234, 241, 248, 255, 262, 269, 276, 283, 290, 297, 304, 311, 318, 326, 333

Offset: 1

Labos Elemer, Jun 20 2001

Harry J. Smith, Table of n, a(n) for n = 1..2000

Cf. A000312, A029837, A003070, A045716.

a(n) = { if(n<=1, 0, logint(n^n-1, 2) + 1) } \\ Harry J. Smith, Jul 26 2009

a(n) = ceiling(log_2(n^n)) = A029837(A000312(n)).

Offset changed from 0 to 1 by Harry J. Smith, Jul 26 2009

A214047 Least m>0 such that n! <= (3/2)^m.

Original entry on oeis.org

1, 2, 5, 8, 12, 17, 22, 27, 32, 38, 44, 50, 56, 63, 69, 76, 83, 90, 98, 105, 112, 120, 128, 136, 144, 152, 160, 168, 176, 185, 193, 202, 210, 219, 228, 237, 245, 254, 263, 273, 282, 291, 300, 310, 319, 328, 338, 347, 357, 367

Offset: 1

Clark Kimberling, Jul 18 2012

			a(6) = 17 because (3/2)^16 < 6! <= (3/2)^17.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A003070, A213857.

Table[m=1; While[n!>(3/2)^m, m++]; m, {n,1,100}]
Join[{1},With[{c=Log[3/2]},Table[Ceiling[Log[n!]/c],{n,2,50}]]] (* Harvey P. Dale, May 15 2013 *)

A061716 Binary order of n-th prime.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10

Offset: 1

Labos Elemer, Jun 20 2001

nonn

Apart from the first terms, the same as A035100. - R. J. Mathar, Oct 02 2008

Harry J. Smith, Table of n, a(n) for n = 1..2000

Cf. A029837, A000040, A003070, A045716, A045716, A036378.

Ceiling[Log2[Prime[Range[110]]]] (* Harvey P. Dale, Apr 12 2023 *)

a(n) = { logint(prime(n)-1, 2) + 1 } \\ Harry J. Smith, Jul 26 2009

a(n) = ceiling(log_2(prime(n))) = A029837(A000040(n)).

Offset changed from 0 to 1 by Harry J. Smith, Jul 26 2009

cp's OEIS Frontend

A067850 Highest power of 2 not exceeding n!.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A049775 a(n) is the sum of all integers from 2^(n-2)+1 to 2^(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A072831 Number of bits in n!.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A213857 Least m such that n! <= 3^m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica