For a positive integer $n$, the prime omega function value $\Omega(n):=\sum\_{p\mid n}{\nu\_p(n)}$ counts the number of prime divisors of $n$ with multiplicities. A result of Hardy and Wright, [1, Theorem 430 on p. 472], implies that $\frac{1}{x}\sum\_{n\leq x}{\Omega(n)}\sim\log\log{x}$ as $x\to\infty$.


**Question:**
Letting the variable $q$ range over prime powers, is it true that


$\left(\sum\_{q\leq x}{1}\right)^{-1}\cdot\sum\_{q\leq x}{\Omega(q-1)}\sim\log\log{x}$


as $x\to\infty$?


This question is motivated by some work in progress concerning certain algorithms over finite fields $\mathbb{F}\_q$. An affirmative answer would imply that these algorithms are efficient for "most" finite fields. In fact, it would suffice if


$\left(\sum\_{q\leq x}{1}\right)^{-1}\sum\_{q\leq x}{\operatorname{mpe}(q-1)}\in O(\log\log{x})$


where $\operatorname{mpe}(n):=\max\_{p\mid n}{\nu\_p(n)}\leq\Omega(n)$. The following table provides some computational evidence, namely the values of $f(x):=\left(\log\log{x}\sum\_{q\leq x}{1}\right)^{-1}\sum\_{q\leq x}{\Omega(q-1)}$ for $x=10^n$ with $n\in\{5,6,7,8,9\}$.





| $x$ | $10^5$ | $10^6$ | $10^7$ | $10^8$ | $10^9$ |
| --- | --- | --- | --- | --- | --- |
| $f(x)$ | 1.91446 | 1.86387 | 1.82433 | 1.7924 | 1.76574 |



Reference:


[1] G.H. Hardy and E.M. Wright, *An Introduction to the Theory of Numbers. Edited and revised by D.R. Heath-Brown and J.H. Silverman. With a foreword by Andrew Wiles*, Oxford University Press, Oxford, 6th edn. 2008.



Average value of the prime omega function $\Omega$ on predecessors of prime powers
Yes, this is true.


First, let us observe that replacing prime powers with primes cannot make a difference, and the same goes to replacing $\Omega$ with $\omega$.


Erdős, in "On the normal number of prime factors of $p-1$ and some related problems concerning Euler’s $\phi$-function (Quart. Journ. of Math. 6, 205-213 (1935)) proved a Hardy--Ramanujan result for $\omega(p-1)$, namely that $\omega(p-1) \sim \log \log p$ for almost all $p$.


C. B. Haselgrove, in "Some theorems in the analytic theory of numbers" (J. Lond. Math. Soc. 26, 273-277 (1951)), proved that
$$\frac{\sum\_{p \le x} \omega(p-1)}{\sum\_{p \le x}1}\sim \log \log x.$$
In fact, he computed any fixed moment.


H. Halberstam in "On the distribution of additive number-theoretic functions. III." (J. London Math. Soc. 31 (1956), 14–27) extended Haselgrove's result to $\omega(f(p))$ for any irreducible $f \in \mathbb{Z}[x]$.


A central limit theorem can be proved for $\omega(p-1)$, and this is due to Barban (according to Elliott's book mentioned below). Some modern references for this:


1. Peter D. T. A. Elliott, "Probabilistic number theory. II", Mathematischen Wissenschaften 240. Springer-Verlag, Berlin-New York, 1980.
2. Krishnaswami Alladi, "Moments of additive functions and the sequence of shifted primes", Pacific J. Math. 118 (1985), no. 2, 261–275.
3. Andrew Granville and Kannan Soundararajan, "Sieving and the Erdős-Kac theorem", Equidistribution in number theory, an introduction, 15–27, NATO Sci. Ser. II Math. Phys. Chem., 237, Springer, Dordrecht, 2007.


