15 votos

Es $\ 7!=5040\ $ la más grande altamente compuesto factorial?

Altamente número compuesto es un número natural $\ n\ge 1\ $ que tiene más divisores que cualquier menor número natural $\ m\ge 1$.

La comprobación de la $\ 1000\ $ entradas en la OEIS-secuencia, me di cuenta de que sólo las siguientes factoriales son altamente compuesto de :

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

Se sabe si $\ 7!=5040\ $ es el más grande altamente compuesto factorial ?

El factoriales tienen algunas condiciones necesarias para que un número altamente compuesto de :

  • Ellos contienen la primera $k$ números primos como factores primos.
  • Los exponentes son no creciente.
  • El exponente correspondiente a la mayor factor primo es $\ 1$.

Así que, no es evidente si la lista está completa.

13voto

Thomas Puntos 196

Supongamos $n \ge 20$. Trivialmente, $n!$ entonces es divisible por $16$, lo $\dfrac{13}{16}n!$ es un número entero menor que $n!$.

Vamos a la factorización en primos de $n!$$n! = 2^{e_1}3^{e_2}\cdots11^{e_5}13^{e_6}17^{e_7}\cdots p_r^{e_r}$.

Entonces la factorización prima de $\dfrac{13}{16}n!$$\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}$.

Entonces, el número de divisores de a $n!$ $\sigma_0(n!) = (e_1+1)(e_6+1)\displaystyle\prod_{k \neq 1,6}(e_k+1)$ y el número de divisores de a$\dfrac{13}{16}n!$$\sigma_0(\dfrac{13}{16}n!) = (e_1-3)(e_6+2)\displaystyle\prod_{k \neq 1,6}(e_k+1)$.

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

El uso de la bien conocida fórmula para la potencia más grande de un primer dividir un factorial, hemos

$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$.

Del mismo modo, $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}$. Por lo tanto, $4e_6+7 \le \dfrac{n}{3}+7$.

Lo voy a dejar como un ejercicio para demostrar que $\dfrac{n}{3}+7 < n - 2 - \log_2 n$ tiene para todos los enteros $n \ge 20$.

Por lo tanto, para todos los enteros $n \ge 20$,$4e_6+7 \le \dfrac{n}{3}+7 < n - 2 - \log_2 n < e_1$, y por lo tanto, $\sigma_0(\dfrac{13}{16}n!) > \sigma_0(n!)$.

Por eso, $n!$ no es muy compuesto por $n \ge 20$. Ahora, queda por comprobar si cualquier factoriales entre el $7!$ $20!$ son altamente compuesto.

EDIT: de la lista de los primeros 1000 altamente compuesto de números que OP mencionado, parece que el $149$-ésimo más grande altamente número compuesto es $\approx 1.49 \times 10^{17}$, mientras que $19! \approx 1.22 \times 10^{17}$. Ninguno de los números de $8!, 9!, \ldots, 19!$ a aparecer en la lista, por lo $7!$ es de hecho el más grande altamente compuesto factorial.

2voto

Shabaz Puntos 403

Sí, es conocido. Si se mira el número de divisores de función, un número $n$ con la descomposición en factores primos $p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots$ $\sigma_0(n)=(a_1+1)(a_2+1)(a_3+1)\ldots$ divisores. El factoriales tienen también muchos pequeños factores. Cada vez que se multiplica por el primer doble del número de divisores, pero al aumentar el poder de $2$ $n$ $n+1$sólo multiplicar el número de divisores por $\frac {n+2}{n+1}=1+\frac 1{n+1}$. El algoritmo voraz para encontrar altamente compuesto de números podría mirar a $\log \sigma_0(n)$. Si se multiplica $n$ por un primer $p$ que se encuentra actualmente en la factorización de $n$ $p^a$ agregar $\log 1+\frac 1{a+1}$ en el registro de la cantidad de factores y agregar a $\log p$ para el registro de $n$, por lo que la relación costo/beneficio de cada incremento es $\frac {\log 1+\frac 1{a+1}}{\log p}$ Búsqueda a través de los números primos, de encontrar el mejor, y que es el siguiente multiplicador. Cuando usted mira OEIS A002182 no cada entrada es un múltiplo de la anterior, pero veo que hay muchos pequeños factores, entre los factoriales. $n!$ sobre $\frac n2$ factores de $2$, por ejemplo. Realmente justificar esto usted necesita para usar el teorema de los números primos para mostrar cómo es de grande el próximo primer será, a continuación, mostrar desea utilizar antes de $n!$. Usted puede encontrar un límite finito de factoriales que son candidatos, a continuación, compruebe ellos.

1voto

Stephan Aßmus Puntos 16

Lo que te falta es la relación de los exponentes. Para factoriales, por el teorema de Legendre, el exponente de $p$ es proporcional a $1/p.$ supongo que es un poco más preciso decir proporcional a $1 /(p-1).$

El superior altamente compuesto de números de exponentes para cada primer proporcional a $1/ \log p.$ Tipo Robin hizo un método de interpolación entre consecutivos SHC números de construir todos los altamente compuesto entre los números. El punto es que es altamente compuesto números son, en el largo plazo, similar a la del mínimo común múltiplo de los números de $1$ algunos $m.$

Podría ser una buena oferta de trabajo para mostrar que $5040$ es la última factorial que funciona, pero está claro que sólo hay un número finito de estos, y de límites explícitos podría ser construido. Desde la salida a continuación, puede ver cuánto más pequeña es una SHC número puede ser, sin embargo, tienen más divisores que el factorial bajo consideración. Los logaritmos son de base diez.

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

Hizo uno solo un poco más alto, pero sin la factorizations, sólo el número de divisores y el logaritmo base diez.

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 

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X