5
$\begingroup$

An exercise:

Using the prime number theorem find an asymptotic expression for $d(n!)$ where $d$ is the number of divisors.

  • 0
    What do you mean by $d(n!)$?2011-11-29
  • 0
    corrected, thanks.2011-11-29
  • 0
    You might want to have a look [here (OEIS)](http://oeis.org/A027423).2011-11-29
  • 1
    $d$ is multiplicative so write $n!=\prod_{p\le n}p^{v_p(n)}$ where each $v_p(n)=\sum_{l=1}\lfloor n/p^l\rfloor$, then $$d(n!)=\prod_{p\le n}\left(1+\sum_{l=1}\left\lfloor\frac{n}{p^l}\right\rfloor\right)\le \prod_{p\le n}\left(1+\frac{n}{p-1}\right)$$ which is bounded below by $n^{\pi(n)}/n\#$ and above by $n^{\pi(n)}/\prod(1-1/p)$. I'll see if I can flesh this out later.2011-11-29

3 Answers 3

6

The prime power-decomposition of $n!$ is well-known: $$ n! = p_1^{e_1} \times \cdots \times p_k^{e_k} $$ where $e_i = \left\lfloor \frac{n - s(p_i,n)}{p_i-1} \right\rfloor$, where $s(b,n)$ is sum of digits of number $n$ in base $b$. Thus $$ 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) $$

Reasonably efficient code to compute $d(n!)$ in Mathematica is

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

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

The last half of $\{ e_i \}_{i=1}^k$ consists of ones, making $d(n!) \ge 2^{\Pi(n)}$ for all $n \ge 1$. The following plot suggests $d(n!) \sim O\left(\frac{\mathrm{e}^n}{n}\right)$:

enter image description here

4

Just to be annoying, taking $n!$ is not the most efficient way to get a large number of divisors. There is a recipe, which takes as parameter some real number $\delta > 0,$ and gives the exponent on each prime factor of a (very large) number, call it $N_\delta.$ the exponent of the prime $p$ is given by $$ \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor $$ which gives nonzero coefficients as long as $p^\delta \leq 2,$ that is $p \leq 2^{1/\delta}.$

An unusually rough approximation is $$ N_\delta \approx e^{2^{1/\delta}} $$

So, $$ N_\delta \; = \; \prod_{p} \; p^{ \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor} $$ Note that the exponents are non-increasing and eventually zero, this is a finite product.

The number $N_\delta$ gives the largest possible value, among all positive integers $n,$ of $$ \frac{d(n)}{n^\delta}.$$ If the optimum should be achieved at more than one integer $n,$ the set is nevertheless finite and our $N_\delta$ is the largest number in the set.

See http://en.wikipedia.org/wiki/Superior_highly_composite_number as well as http://oeis.org/A002201

The definition tells us some quick theorems, $$ d(n) \leq \sqrt{12 n} $$ and $$ d(n) \; \leq \; \; 24 \; \; \left( \frac{n}{315} \right)^{(1/3)} $$ More elaborate work gives $$ d(n) \; \leq \; \; n^{\frac{1.0660186782977...}{\log \log n}}$$ with equality only at $n = 6,983,776,800,$ this number being $N_\delta$ when $\delta = 0.23,$ and $d(N_\delta) = 2304.$

From pages 260-266 in Hardy and Wright, we find Theorem 317, $$ \limsup \frac{\log d(n) \log \log n}{\log n} = \log 2 $$

We can give this quantitative shape with $$ d(n) \; \leq \; \; n^{\left(\frac{\log 2}{\log \log n}\right) \left( 1 + \frac{1.93485096797...}{\log \log n} \right)}$$ with equality only at $n =N_\delta$ for $\delta = 0.155,$ and $N_\delta \approx 6.929 \times 10^{40},$ and $d(N_\delta) = 764,411,904 \approx 7.6 \times 10^8.$

1

The answer is $$\log d(n!)=c \frac{n}{\log n}+O(\frac{n}{\log^2 n}\log \log n) \ \ (*)$$ where $$c:=\sum_{k \geq 1}\frac{\log(1+\frac{1}{k})}{k}$$To prove this we break the sum $$\log d(n!)=\sum_{p\leq n} \log (1+v_p(n))$$ into the sum over $ p \leq \frac{n}{\log n}$ and into $ \frac{n}{\log n}

We begin by finding an upper bound for each term of the sum: $$v_p(n)=\sum_{k \geq 1}[\frac{n}{p^k}] \leq \frac{n}{p-1}$$ and hence $1+u_p(n) \leq 3 \frac{n}{p}$ from which we get $$\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 $$ The last inequality comes from the PNT estimates $$\pi(x)=\frac{x}{\log x}+O(\frac{x}{\log^2x}) , \theta(x)=x+O(\frac{x}{\log x})$$ Using stronger versions of the PNT, one might get a better approximation for the error term in (*).

The remaining region is over $p \in (\frac{n}{\log n},n].$ The union of the disjoint intervals $$I_k:=(\frac{n}{k+1},\frac{n}{k}] \ \ k=1,2,..,m:=[\log n]$$ certainly covers the remaining region. The union might extend a bit to the left of $\frac{n}{\log n}$, namely it is contained in $(\frac{n}{\log n}-2\frac{n}{\log^2 n},n].$ Notice that $u_p(n)=k$ when $p \in I_k$. Therefore, the "main term" sum is equal to $$ \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)$$ where the error term comes from the contribution of the primes in $ (\frac{n}{\log n}-2\frac{n}{\log^2 n},\frac{n}{\log n}].$ The sum is equal to $$\sum_{k=1}^m \log(1+\frac{1}{k}) \pi(n/k)-\log(1+m)\pi(n/m)$$ Using the PNT in the aforementioned form one arrives at (*) by a finite amount of computation. The fact that $k \ll \log n$ is very handy for these computations since it provides the equality $\frac{1}{\log(n/k)}=\frac{1}{\log n}(1+O(\log \log n/\log n))$. One also uses $\sum_{k>m}\frac{\log(1+k^{-1})}{k}\ll \sum_{k>m} k^{-2} \ll \frac{1}{m}$