Evaluar $d(n!)$

Question

Un ejercicio:

Utilizando el teorema de los números primos encuentre una expresión asintótica para $d(n!)$ donde $d$ es el número de divisores.

Answer 1

La descomposición primaria de la potencia de $n!$ es bien conocida: $$ n! = p_1^{e_1} \times \cdots \times p_k^{e_k} $$ donde $e_i = \left\lfloor \frac{n - s(p_i,n)}{p_i-1} \right\rfloor$ , donde $s(b,n)$ es la suma de dígitos del número $n$ en la base $b$ . Así, $$ d(n!) = \prod_{i=1}^k (e_i+1) = \prod_{i=1}^k \left( \left\lfloor \frac{n - s(p_i,n)}{p_i-1} \right\rfloor + 1 \right) $$

Código razonablemente eficiente para calcular $d(n!)$ en Mathematica es

FactorialPrimeExponent[n_, p_] := 
 Quotient[n - Total[IntegerDigits[n, p]], p - 1]

FactorialDivisorCount[n_Integer] := 
 Apply[Times, (FactorialPrimeExponent[n, #] & /@ 
     Prime[Range[PrimePi[n]]]) + 1]

La última mitad de $\{ e_i \}_{i=1}^k$ se compone de unos, haciendo $d(n!) \ge 2^{\Pi(n)}$ para todos $n \ge 1$ . El siguiente gráfico sugiere $d(n!) \sim O\left(\frac{\mathrm{e}^n}{n}\right)$ :

Answer 2

Sólo para molestar, tomando $n!$ no es la forma más eficiente de obtener un gran número de divisores. Hay una receta, que toma como parámetro algún número real $\delta > 0,$ y da el exponente de cada factor primo de un número (muy grande), llámalo $N_\delta.$ el exponente del primo $p$ viene dada por $$ \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor $$ que da coeficientes no nulos siempre que $p^\delta \leq 2,$ es decir $p \leq 2^{1/\delta}.$

Una aproximación inusual es $$ N_\delta \approx e^{2^{1/\delta}} $$

Así que, $$ N_\delta \; = \; \prod_{p} \; p^{ \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor} $$ Nótese que los exponentes son no crecientes y eventualmente cero, se trata de un producto finito.

El número $N_\delta$ da el mayor valor posible, entre todos los enteros positivos $n,$ de $$ \frac{d(n)}{n^\delta}.$$ Si el óptimo debe alcanzarse en más de un número entero $n,$ el conjunto es, sin embargo, finito y nuestro $N_\delta$ es el mayor número del conjunto.

Ver http://en.wikipedia.org/wiki/Superior_highly_composite_number así como http://oeis.org/A002201

La definición nos indica algunos teoremas rápidos, $$ d(n) \leq \sqrt{12 n} $$ y $$ d(n) \; \leq \; \; 24 \; \; \left( \frac{n}{315} \right)^{(1/3)} $$ Un trabajo más elaborado da $$ d(n) \; \leq \; \; n^{\frac{1.0660186782977...}{\log \log n}}$$ con igualdad sólo en $n = 6,983,776,800,$ siendo este número $N_\delta$ cuando $\delta = 0.23,$ y $d(N_\delta) = 2304.$

En las páginas 260-266 de Hardy y Wright, encontramos el teorema 317, $$ \limsup \frac{\log d(n) \log \log n}{\log n} = \log 2 $$

Podemos dar esta forma cuantitativa con $$ d(n) \; \leq \; \; n^{\left(\frac{\log 2}{\log \log n}\right) \left( 1 + \frac{1.93485096797...}{\log \log n} \right)}$$ con igualdad sólo en $n =N_\delta$ para $\delta = 0.155,$ y $N_\delta \approx 6.929 \times 10^{40},$ y $d(N_\delta) = 764,411,904 \approx 7.6 \times 10^8.$

Answer 3

La respuesta es $$\log d(n!)=c \frac{n}{\log n}+O(\frac{n}{\log^2 n}\log \log n) \ \ (*)$$ donde $$c:=\sum_{k \geq 1}\frac{\log(1+\frac{1}{k})}{k}$$ Para demostrarlo rompemos la suma $$\log d(n!)=\sum_{p\leq n} \log (1+v_p(n))$$ en la suma sobre $ p \leq \frac{n}{\log n}$ y en $ \frac{n}{\log n}<p \leq n.$ El primer caso dará el término de error y el segundo el término principal de (*).

Empezamos por encontrar un límite superior para cada término de la suma: $$v_p(n)=\sum_{k \geq 1}[\frac{n}{p^k}] \leq \frac{n}{p-1}$$ y por lo tanto $1+u_p(n) \leq 3 \frac{n}{p}$ de la que obtenemos $$\sum_{p \leq \frac{n}{\log n}} \log (1+u_p(n)) \leq \log 3 \pi(\frac{n}{\log n})+(\log n) \pi(\frac{n}{\log n})-\theta(\frac{n}{\log n}) \ll \frac{n}{\log^2 n}\log \log n $$ La última desigualdad proviene de las estimaciones de la PNT $$\pi(x)=\frac{x}{\log x}+O(\frac{x}{\log^2x}) , \theta(x)=x+O(\frac{x}{\log x})$$ Utilizando versiones más fuertes de la PNT, se podría obtener una mejor aproximación para el término de error en (*).

El resto de la región es más $p \in (\frac{n}{\log n},n].$ La unión de los intervalos disjuntos $$I_k:=(\frac{n}{k+1},\frac{n}{k}] \ \ k=1,2,..,m:=[\log n]$$ ciertamente cubre el resto de la región. La unión podría extenderse un poco a la izquierda de $\frac{n}{\log n}$ , es decir, está contenida en $(\frac{n}{\log n}-2\frac{n}{\log^2 n},n].$ Observe que $u_p(n)=k$ cuando $p \in I_k$ . Por lo tanto, la suma del "término principal" es igual a $$ \sum_{k=1}^{m} \log(1+k)(\pi(\frac{n}{k+1})-\pi(\frac{n}{k}))+O(\frac{n}{\log^2 n}\log \log n)$$ donde el término de error proviene de la contribución de los primos en $ (\frac{n}{\log n}-2\frac{n}{\log^2 n},\frac{n}{\log n}].$ La suma es igual a $$\sum_{k=1}^m \log(1+\frac{1}{k}) \pi(n/k)-\log(1+m)\pi(n/m)$$ Utilizando la PNT en la forma mencionada se llega a (*) mediante una cantidad finita de cálculos. El hecho de que $k \ll \log n$ es muy útil para estos cálculos ya que proporciona la igualdad $\frac{1}{\log(n/k)}=\frac{1}{\log n}(1+O(\log \log n/\log n))$ . También se utiliza $\sum_{k>m}\frac{\log(1+k^{-1})}{k}\ll \sum_{k>m} k^{-2} \ll \frac{1}{m}$