The excess of an integer $n$

Question

How can one find an estimate for $$\sum_{p \text{ prime,}\ k\geq 2:p^k|n}1$$ The reason is to show that the normal value of $\Omega(n)$ is $\log\log n$, the same as that of $\omega(n)$.

Answer 1

Your sum has average value of approximately 0.77. Following is a proof that the sum has an average value less than one.

My source of information comes mostly from Chapter 8 of I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991.

\begin{align} \sum_{n \le x} \sum_{\substack{p^k | n\\ k \ge 2}} 1 & = \sum_{\substack{p^k,\ m\\ p^km \le x\\ k \ge 2}} 1 &&\text{($n = p^km$)}\\ & = \sum_{\substack{p^k \le x\\ k \ge 2}} \left\lfloor \frac x{p^k} \right\rfloor\\ & = \sum_{\substack{p^k \le x\\ k \ge 2}} \left( \frac x{p^k} + O(1) \right)\\ & = x \sum_{\substack{p^k \le x\\ k \ge 2}} \frac 1{p^k} + O\left( \sum_{\substack{p^k \le x\\ k \ge 2}} 1 \right)\\ & = x \sum_{\substack{p \le x^{1/k}\\ k \ge 2}} \frac 1{p^k} + O\left( \sum_{\substack{p \le x^{1/k}\\ k \ge 2}} 1 \right)\\ & \le x \sum_{\substack {p\\ k \ge 2}} \frac 1{p^k} + O\left( \sum_{k \ge 2} \pi\left(x^{1/k}\right) \right) &&\text{($\pi$ is the prime-counting function)}\\ & = x \sum_p \frac 1{p(p-1)} + O(\sqrt x \log x) &&\text{(sum of the geometric series)}\\ & \le x \sum_{j = 2}^\infty \frac 1{j(j-1)} + O(\sqrt x \log x)\\ & = x + O(\sqrt x \log x) &&\text{(the sum equals $1$)} \end{align} That shows that the coefficient of $x$ in the line before the first inequality is less than one. Thus, your sum has an average value less than one.

To check that conclusion, I fit a line to $f(x) = \sum_{n \le x} \sum_{p^k | n, k \ge 2} 1 = \sum_{n \le x} (\Omega(n) - \omega(n))$ versus $x$ for $x = 1, 2, 3, \ldots, 100000$ and got $f(x) \approx 0.7725x - 45.00$ and, if the intercept is forced to be zero, $f(x) \approx 0.7718x$, both with coefficient of determination greater than $0.9999997$. The arithmetic average of those $\Omega(x) - \omega(x)$ is approximately $0.7721$.

That explains why the average value of $\Omega(n)$ is $\log \log n$, the same as that of $\omega(n)$. $\Omega(n)$ is equal to $\omega(n)$ plus contributions from higher powers of $p$, but we have just shown that those contributions are of normal order (because the average order that we determined is for a non-negative function) less than $\log \log n$.

See also Martin Klazar's lecture notes "Introduction to Number Theory," Section 4.3.