What is the limit of $\frac{\Omega(n!)}{n}$ as $n \to \infty$?

Question

Let $p_i$ be the $i$th prime number, and $\Omega(n) =$ the total number of prime factors of $n$ counting multiplicities. We know that $\Omega(n)$ is completely additive, so:

  $$ \frac{\Omega(n!)}{n} = \sum_{i = 1}^n \Omega(i) = \frac{1}{n}\sum_{k = 1}^{\pi(n)}\sum_{j = 1}^{\log_{p_k}(n)}\left\lfloor\frac{n}{p_k^j} \right\rfloor = \\ \ \\ \frac{1}{n}\sum_{k = 1}^{\pi(n)}\sum_{j = 1}^{\log_{p_k}(n)}\frac{n - (n \mod p_k^j)}{p_i^j} = \\ \ \\ \sum_{k = 1}^{\pi(n)}\sum_{j = 1}^{\log_{p_k}(n)}\left(\frac{1}{p_k^j} -\frac{(n \mod p_k^j)}{p_k^jn} \right) $$

I'm thinking since the (infinite) sum contains $\frac{1}{p_i}, i=1..\infty$. It makes me think it probably diverges. However, when computing it it seems to be approaching the line $y = 4$ as in $\lim_{n \to \infty} \frac{\Omega(n!)}{n} = 4$; either that or it's actually going up very slowly (logarithmically), which still means it diverges. Just would have to plug in a googleplex to get it past $y = 4$.

Here is some code to experiment with:

from sympy import *
import matplotlib.pyplot as plt

def f(n):
    S = 0
    for i in range(1, n+1):
        S += primeomega(i)
    return S

k = 1
N = 6000000
X = []
Y = []
stride = 1

for n in range(1000000, N, stride):
    F = float(f(n) / n)
    
    print(n, F)
    X.append(n)
    Y.append(F)
    
    
plt.plot(X, Y)
plt.show()

So what does this relative growth of $\Omega(n!)$ look like? Any way using analytic number theory to take its density limit?

Answer 1

Your limit is infinity.

Let $\omega(n)$ be the number of distinct prime factors of $n$. We have $\omega(n)\leq \Omega(n)$.

Since $\Omega$ is completely additive, $\Omega(n!)=\sum_{k\leq n}\Omega(k)$.

This gives $\Omega(n!)\geq \sum_{k\leq n} \omega(k)$.

A standard method switching order of summation applies, $$\begin{align} \sum_{k\leq n}\omega(k)&=\sum_{k\leq n}\sum_{p|k}1\\ &=\sum_{p\leq n}\sum_{k\leq n/p}1\\ &=\sum_{p\leq n}\left(\frac np + O(1)\right)\\ &=n\log\log n +O(n)+O(\pi(n)) \end{align} $$ where $\log$ is the natural log and $\pi(n)$ is the number of primes up to $n$.

Then $$ \frac{\Omega(n!)}n\geq \log\log n +O(1)+ O(\frac{\pi(n)}n). $$ By $\pi(n)=O(n/\log n)$, we obtain $$ \frac{\Omega(n!)}n\geq \log\log n + O(1)+ O(\frac1{\log n}). $$ The right side diverges to infinity.

Answer 2

This answer is to give an asymptotic formula for $\Omega(n!)$:

\begin{aligned} \Omega(n!) &=\sum_{k\le n}\Omega(k)=\sum_{k\le n}\sum_{p^a\|k}a=\sum_{a\le\log_2n}a\sum_{p\le n}\sum_{\substack{k\le n\\p^a|k,p^{a+1}\nmid k}}1 \\ &=\sum_{a\le\log_2n}a\sum_{p\le n}\left(\left\lfloor n\over p^a\right\rfloor-\left\lfloor n\over p^{a+1}\right\rfloor\right) =\sum_{a\le\log_2n}a\sum_{p\le n}\left({n\over p^a}-{n\over p^{a+1}}+O(1)\right) \\ &=n\sum_{p\le n}\sum_{a\le\log_2n}{(p-1)a\over p^{a+1}}+O(\log^2n) \\ &=n\left(\sum_{p\le n}\frac1p-\sum_{p\le n}{1\over p^2}+\sum_{p\le n}\sum_{1<a\le\log_2n}{(p-1)a\over p^{a+1}}\right)+O(\log^2n). \end{aligned}

By Mertens' formula, there is

$$ \sum_{p\le n}\frac1p=\log\log n+B+O\left(1\over\log n\right), $$

where the constant $B$ evaluates to

$$ B=\gamma+\sum_p\left\{\log\left(1-\frac1p\right)+\frac1p\right\}. $$

Differentiating the formula for geometric series gives

$$ \sum_{1<a\le\log_2n}{(p-1)a\over p^{a+1}}={2p-1\over p^2(p-1)}+O\left(\frac1n\right), $$

so combining everything gives

$$ \Omega(n!)=n(\log\log n+C)+O\left(n\over\log n\right), $$

where

\begin{aligned} C &=B-\sum_p{1\over p^2}+\sum_p{2p-1\over p^2(p-1)} \\ &=B+\sum_p{1\over p(p-1)}. \end{aligned}