13
$\begingroup$

A highly composite number is a natural number $\ n\ge 1\ $ that has more divisors than any smaller natural number $\ m\ge 1$.

Checking the $\ 1000\ $ entries in the OEIS-sequence, I noticed that only the following factorials are highly composite :

$$[1, 2, 6, 24, 120, 720, 5040]$$

Is it known whether $\ 7!=5040\ $ is the largest highly composite factorial ?

The factorials have some conditions necessary for a number to be highly composite :

  • They contain the first $k$ prime numbers as prime factors.
  • The exponents are non-increasing.
  • The exponent corresponding to the largest prime factor is $\ 1$.

So, it is not obvious whether the above list is complete.

$\endgroup$
  • $\begingroup$ If a number is divisible by $4$, does $2$ also count as a divisor? $\endgroup$ – Simply Beautiful Art Aug 7 '16 at 0:05
  • $\begingroup$ @SimpleArt: Yes.en.wikipedia.org/wiki/Divisor $\endgroup$ – Jonas Meyer Aug 7 '16 at 0:06
  • $\begingroup$ Aren't the properties above true for any $p!$, $p$ prime? For instance, $11! = 39916800 = 2^8 \times 3^4 \times 5^2 \times 7^1 \times 11^1$. $\endgroup$ – Brian Tung Aug 7 '16 at 0:09
  • $\begingroup$ I mean, $11!$ turns out not to be highly composite, I think. But there must be tighter conditions on this property. I can't see what the answer is. $\endgroup$ – Brian Tung Aug 7 '16 at 0:12
  • 2
    $\begingroup$ The properties I mentioned are only necessary, not sufficient, for a number to be highly composite, but every factorial satisfies them (not only $p!$ with $p$ prime). $\endgroup$ – Peter Aug 7 '16 at 0:13
9
$\begingroup$

Suppose $n \ge 20$. Trivially, $n!$ is then divisible by $16$, so $\dfrac{13}{16}n!$ is an integer smaller than $n!$.

Let the prime factorization of $n!$ be $n! = 2^{e_1}3^{e_2}\cdots11^{e_5}13^{e_6}17^{e_7}\cdots p_r^{e_r}$.

Then the prime factorization of $\dfrac{13}{16}n!$ is $\dfrac{13}{16}n! = 2^{e_1-4}3^{e_2} \cdots11^{e_5}13^{e_6+1}17^{e_6}\cdots p_r^{e_r}$.

Then, the number of divisors of $n!$ is $\sigma_0(n!) = (e_1+1)(e_6+1)\displaystyle\prod_{k \neq 1,6}(e_k+1)$ and the number of divisors of $\dfrac{13}{16}n!$ is $\sigma_0(\dfrac{13}{16}n!) = (e_1-3)(e_6+2)\displaystyle\prod_{k \neq 1,6}(e_k+1)$.

Hence, $\sigma_0(\dfrac{13}{16}n!) > \sigma_0(n!)$ iff $(e_1-3)(e_6+2) > (e_1+1)(e_6+1)$ iff $e_1 > 4e_6+7$.

Using the well known formula for the largest power of a prime dividing a factorial, we have

$e_1 = \displaystyle\sum_{k = 1}^{\left\lfloor \log_2 n\right\rfloor}\left\lfloor \dfrac{n}{2^k} \right\rfloor > \displaystyle\sum_{k = 1}^{\left\lfloor \log_2 n\right\rfloor} \left(\dfrac{n}{2^k} - 1\right) \ge n - \dfrac{n}{2^{\left\lfloor \log_2 n\right\rfloor}} - \left\lfloor \log_2 n\right\rfloor \ge n - 2 - \log_2 n$.

Similarly, $e_6 = \displaystyle\sum_{k = 1}^{\left\lfloor \log_{13} n\right\rfloor}\left\lfloor \dfrac{n}{13^k} \right\rfloor \le \displaystyle\sum_{k = 1}^{\left\lfloor \log_{13} n\right\rfloor}\dfrac{n}{13^k} \le \dfrac{n}{12}$. Hence, $4e_6+7 \le \dfrac{n}{3}+7$.

I'll leave it as an exercise to show that $\dfrac{n}{3}+7 < n - 2 - \log_2 n$ holds for all integers $n \ge 20$.

Therefore, for all integers $n \ge 20$, we have $4e_6+7 \le \dfrac{n}{3}+7 < n - 2 - \log_2 n < e_1$, and thus, $\sigma_0(\dfrac{13}{16}n!) > \sigma_0(n!)$.

So, $n!$ is not highly composite for $n \ge 20$. Now, it remains to check if any factorials between $7!$ and $20!$ are highly composite.

EDIT: From the list of the first 1000 highly composite numbers that OP mentioned, it appears that the $149$-th largest highly composite number is $\approx 1.49 \times 10^{17}$, while $19! \approx 1.22 \times 10^{17}$. None of the numbers $8!, 9!, \ldots, 19!$ appear in that list, so $7!$ is indeed the largest highly composite factorial.

$\endgroup$
1
$\begingroup$

Yes, it is known. If you look at the number of divisors function, a number $n$ with prime factorization $p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots$ has $\sigma_0(n)=(a_1+1)(a_2+1)(a_3+1)\ldots$ divisors. The factorials have too many small factors. Every time you multiply by a prime you double the number of divisors, but when you increase the power of $2$ from $n$ to $n+1$ you only multiply the number of divisors by $\frac {n+2}{n+1}=1+\frac 1{n+1}$. The greedy algorithm for finding highly composite numbers would look at $\log \sigma_0(n)$. If you multiply $n$ by a prime $p$ that is currently in the factorization of $n$ as $p^a$ you add $\log 1+\frac 1{a+1}$ to the log of the number of factors and you add $\log p$ to the log of $n$, so the benefit/cost ratio of each increase is $\frac {\log 1+\frac 1{a+1}}{\log p}$ Search over the primes, find the best, and that is your next multiplier. When you look at OEIS A002182 not every entry is a multiple of the previous one, but you see there are too many small factors among the factorials. $n!$ has about $\frac n2$ factors of $2$, for example. To really justify this you need to use the prime number theorem to show how large the next prime will be, then show you want to use it before $n!$ will. You can find a finite limit of factorials that are candidates, then check them.

$\endgroup$
1
$\begingroup$

What you are missing is the ratio of exponents. For factorials, by the theorem of Legendre, the exponent of $p$ is proportional to $1/p.$ I suppose it is slightly more accurate to say proportional to $1 /(p-1).$

The superior highly composite numbers have exponents for each prime proportional to $1/ \log p.$ Guy Robin made a method for interpolating between consecutive SHC numbers to construct all highly composite numbers between. The point is that highly composite numbers are, in the long run, similar to the least common multiple of the numbers from $1$ to some $m.$

It might be a good deal of work to show that $5040$ is the last factorial that works, but it is clear that there are only finitely many such, and explicit bounds could be constructed. From the output below, you can see how much smaller an SHC number can be, yet have more divisors than the factorial under consideration. The logarithms are base ten.

jagy@phobeusjunior:~$ ./factorial
2!  2 =  2  div  2  log 0.30103
3!  6 =  2 3  div  4  log 0.778151
4!  24 =  2^3 3  div  8  log 1.38021
5!  120 =  2^3 3 5  div  16  log 2.07918
6!  720 =  2^4 3^2 5  div  30  log 2.85733
7!  5040 =  2^4 3^2 5 7  div  60  log 3.70243
8!  40320 =  2^7 3^2 5 7  div  96  log 4.60552
9!  362880 =  2^7 3^4 5 7  div  160  log 5.55976
10!  3628800 =  2^8 3^4 5^2 7  div  270  log 6.55976
11!  39916800 =  2^8 3^4 5^2 7 11  div  540  log 7.60116
12!  479001600 =  2^10 3^5 5^2 7 11  div  792  log 8.68034
13!  6227020800 =  2^10 3^5 5^2 7 11 13  div  1584  log 9.79428
14!  87178291200 =  2^11 3^5 5^2 7^2 11 13  div  2592  log 10.9404
15!  1307674368000 =  2^11 3^6 5^3 7^2 11 13  div  4032  log 12.1165
16!  20922789888000 =  2^15 3^6 5^3 7^2 11 13  div  5376  log 13.3206
17!  355687428096000 =  2^15 3^6 5^3 7^2 11 13 17  div  10752  log 14.5511
18!  6402373705728000 =  2^16 3^8 5^3 7^2 11 13 17  div  14688  log 15.8063
19!  121645100408832000 =  2^16 3^8 5^3 7^2 11 13 17 19  div  29376  log 17.0851
20!  2432902008176640000 =  2^18 3^8 5^4 7^2 11 13 17 19  div  41040  log 18.3861
21!  51090942171709440000 =  2^18 3^9 5^4 7^3 11 13 17 19  div  60800  log 19.7083
22!  1124000727777607680000 =  2^19 3^9 5^4 7^3 11^2 13 17 19  div  96000  log 21.0508
23!  25852016738884976640000 =  2^19 3^9 5^4 7^3 11^2 13 17 19 23  div  192000  log 22.4125
24!  620448401733239439360000 =  2^22 3^10 5^4 7^3 11^2 13 17 19 23  div  242880  log 23.7927
25!  15511210043330985984000000 =  2^22 3^10 5^6 7^3 11^2 13 17 19 23  div  340032  log 25.1906


jagy@phobeusjunior:~$ ./Superior_Highly_Composite_read
2 =  2  div  2  log 0.30103
6 =  2 3  div  4  log 0.778151
12 =  2^2 3  div  6  log 1.07918
60 =  2^2 3 5  div  12  log 1.77815
120 =  2^3 3 5  div  16  log 2.07918
360 =  2^3 3^2 5  div  24  log 2.5563
2520 =  2^3 3^2 5 7  div  48  log 3.4014
5040 =  2^4 3^2 5 7  div  60  log 3.70243
55440 =  2^4 3^2 5 7 11  div  120  log 4.74382
720720 =  2^4 3^2 5 7 11 13  div  240  log 5.85777
1441440 =  2^5 3^2 5 7 11 13  div  288  log 6.1588
4324320 =  2^5 3^3 5 7 11 13  div  384  log 6.63592
21621600 =  2^5 3^3 5^2 7 11 13  div  576  log 7.33489
367567200 =  2^5 3^3 5^2 7 11 13 17  div  1152  log 8.56534
6983776800 =  2^5 3^3 5^2 7 11 13 17 19  div  2304  log 9.84409
13967553600 =  2^6 3^3 5^2 7 11 13 17 19  div  2688  log 10.1451
321253732800 =  2^6 3^3 5^2 7 11 13 17 19 23  div  5376  log 11.5068
2248776129600 =  2^6 3^3 5^2 7^2 11 13 17 19 23  div  8064  log 12.3519
65214507758400 =  2^6 3^3 5^2 7^2 11 13 17 19 23 29  div  16128  log 13.8143
195643523275200 =  2^6 3^4 5^2 7^2 11 13 17 19 23 29  div  20160  log 14.2915
6064949221531200 =  2^6 3^4 5^2 7^2 11 13 17 19 23 29 31  div  40320  log 15.7828
12129898443062400 =  2^7 3^4 5^2 7^2 11 13 17 19 23 29 31  div  46080  log 16.0839
448806242393308800 =  2^7 3^4 5^2 7^2 11 13 17 19 23 29 31 37  div  92160  log 17.6521
18401055938125660800 =  2^7 3^4 5^2 7^2 11 13 17 19 23 29 31 37 41  div  184320  log 19.2648
791245405339403414400 =  2^7 3^4 5^2 7^2 11 13 17 19 23 29 31 37 41 43  div  368640  log 20.8983

Made one just a little higher but without the factorizations, just the number of divisors and the logarithm base ten.

jagy@phobeusjunior:~$ ./factorial
2!  2  div  2  log 0.30103
3!  6  div  4  log 0.778151
4!  24  div  8  log 1.38021
5!  120  div  16  log 2.07918
6!  720  div  30  log 2.85733
7!  5040  div  60  log 3.70243
8!  40320  div  96  log 4.60552
9!  362880  div  160  log 5.55976
10!  3628800  div  270  log 6.55976
11!  39916800  div  540  log 7.60116
12!  479001600  div  792  log 8.68034
13!  6227020800  div  1584  log 9.79428
14!  87178291200  div  2592  log 10.9404
15!  1307674368000  div  4032  log 12.1165
16!  20922789888000  div  5376  log 13.3206
17!  355687428096000  div  10752  log 14.5511
18!  6402373705728000  div  14688  log 15.8063
19!  121645100408832000  div  29376  log 17.0851
20!  2432902008176640000  div  41040  log 18.3861
21!  51090942171709440000  div  60800  log 19.7083
22!  1124000727777607680000  div  96000  log 21.0508
23!  25852016738884976640000  div  192000  log 22.4125
24!  620448401733239439360000  div  242880  log 23.7927
25!  15511210043330985984000000  div  340032  log 25.1906
26!  403291461126605635584000000  div  532224  log 26.6056
27!  10888869450418352160768000000  div  677376  log 28.037
28!  304888344611713860501504000000  div  917280  log 29.4841
29!  8841761993739701954543616000000  div  1834560  log 30.9465
30!  265252859812191058636308480000000  div  2332800  log 32.4237
31!  8222838654177922817725562880000000  div  4665600  log 33.915
32!  263130836933693530167218012160000000  div  5529600  log 35.4202

jagy@phobeusjunior:~$ ./Superior_Highly_Composite_read
2  div  2  log 0.30103
6  div  4  log 0.778151
12  div  6  log 1.07918
60  div  12  log 1.77815
120  div  16  log 2.07918
360  div  24  log 2.5563
2520  div  48  log 3.4014
5040  div  60  log 3.70243
55440  div  120  log 4.74382
720720  div  240  log 5.85777
1441440  div  288  log 6.1588
4324320  div  384  log 6.63592
21621600  div  576  log 7.33489
367567200  div  1152  log 8.56534
6983776800  div  2304  log 9.84409
13967553600  div  2688  log 10.1451
321253732800  div  5376  log 11.5068
2248776129600  div  8064  log 12.3519
65214507758400  div  16128  log 13.8143
195643523275200  div  20160  log 14.2915
6064949221531200  div  40320  log 15.7828
12129898443062400  div  46080  log 16.0839
448806242393308800  div  92160  log 17.6521
18401055938125660800  div  184320  log 19.2648
791245405339403414400  div  368640  log 20.8983
37188534050951960476800  div  737280  log 22.5704
185942670254759802384000  div  983040  log 23.2694
9854961523502269526352000  div  1966080  log 24.9937
581442729886633902054768000  div  3932160  log 26.7645
1162885459773267804109536000  div  4423680  log 27.0655
12791740057505945845204896000  div  6635520  log 28.1069 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.