# Prime omega function

In number theory, the prime omega functions $\omega (n)$ and $\Omega (n)$ count the number of prime factors of a natural number $n.$ Thereby $\omega (n)$ (little omega) counts each distinct prime factor, whereas the related function $\Omega (n)$ (big omega) counts the total number of prime factors of $n,$ honoring their multiplicity (see arithmetic function). For example, if we have a prime factorization of $n$ of the form $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}$ for distinct primes $p_{i}$ ($1\leq i\leq k$ ), then the respective prime omega functions are given by $\omega (n)=k$ and $\Omega (n)=\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}$ . These prime factor counting functions have many important number theoretic relations.

## Properties and relations

The function $\omega (n)$  is additive and $\Omega (n)$  is completely additive.

$\omega (n)=\sum _{p\mid n}1$

If $p$  divides $n$  at least once we count it only once, e.g. $\omega (12)=\omega (2^{2}3)=2$

$\Omega (n)=\sum _{p^{\alpha }\mid \mid n}\alpha$

If $p$  divides $n$  $\alpha$  times then we count the exponents, e.g. $\Omega (12)=\Omega (2^{2}3^{1})=3$

$\Omega (n)\geq \omega (n)$

If $\Omega (n)=\omega (n)$  then $n$  is squarefree and related to the Möbius function by

$\mu (n)=(-1)^{\omega (n)}=(-1)^{\Omega (n)}$

If $\Omega (n)=1$  then $n$  is a prime number.

It is known that the average order of the divisor function satisfies $2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}$ .

Like many arithmetic functions there is no explicit formula for $\Omega (n)$  or $\omega (n)$  but there are approximations.

An asymptotic series for the average order of $\omega (n)$  is given by 

${\frac {1}{n}}\sum \limits _{k=1}^{n}\omega (k)\sim \log \log n+B_{1}+\sum _{k\geq 1}\left(\sum _{j=0}^{k-1}{\frac {\gamma _{j}}{j!}}-1\right){\frac {(k-1)!}{(\log n)^{k}}},$

where $B_{1}\approx 0.26149721$  is the Mertens constant and $\gamma _{j}$  are the Stieltjes constants.

The function $\omega (n)$  is related to divisor sums over the Möbius function and the divisor function including the next sums.

$\sum _{d\mid n}|\mu (d)|=2^{\omega (n)}$
$\sum _{d\mid n}|\mu (d)|k^{\omega (d)}=(k+1)^{\omega (n)}$
$\sum _{r\mid n}2^{\omega (r)}=d(n^{2})$
$\sum _{r\mid n}2^{\omega (r)}d\left({\frac {n}{r}}\right)=d^{2}(n)$
$\sum _{d\mid n}(-1)^{\omega (d)}=\prod \limits _{p^{\alpha }||n}(1-\alpha )$
$\sum _{\stackrel {1\leq k\leq m}{(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},\ m_{1},m_{2}{\text{ odd}},m=\operatorname {lcm} (m_{1},m_{2})$
$\sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)$

The characteristic function of the primes can be expressed by a convolution with the Möbius function:

$\chi _{\mathbb {P} }(n)=(\mu \ast \omega )(n)=\sum _{d|n}\omega (d)\mu (n/d).$

A partition-related exact identity for $\omega (n)$  is given by 

$\omega (n)=\log _{2}\left[\sum _{k=1}^{n}\sum _{j=1}^{k}\left(\sum _{d\mid k}\sum _{i=1}^{d}p(d-ji)\right)s_{n,k}\cdot |\mu (j)|\right],$

where $p(n)$  is the partition function, $\mu (n)$  is the Möbius function, and the triangular sequence $s_{n,k}$  is expanded by

$s_{n,k}=[q^{n}](q;q)_{\infty }{\frac {q^{k}}{1-q^{k}}}=s_{o}(n,k)-s_{e}(n,k),$

in terms of the infinite q-Pochhammer symbol and the restricted partition functions $s_{o/e}(n,k)$  which respectively denote the number of $k$ 's in all partitions of $n$  into an odd (even) number of distinct parts.

## Continuation to the complex plane

A continuation of $\omega (n)$  has been found, though it is not analytic everywhere. Note that the normalized $\operatorname {sinc}$  function is used.

$\omega (z)=\log _{2}\left(\sum _{x=1}^{\lceil Re(z)\rceil }\operatorname {sinc} \left(\prod _{y=1}^{\lceil Re(z)\rceil +1}\left(x^{2}+x-yz\right)\right)\right)$

## Average order and summatory functions

An average order of both $\omega (n)$  and $\Omega (n)$  is $\log \log n$ . When $n$  is prime a lower bound on the value of the function is $\omega (n)=1$ . Similarly, if $n$  is primorial then the function is as large as $\omega (n)\sim {\frac {\log n}{\log \log n}}$  on average order. When $n$  is a power of 2, then $\Omega (n)\sim {\frac {\log n}{\log 2}}$  .

Asymptotics for the summatory functions over $\omega (n)$ , $\Omega (n)$ , and $\omega (n)^{2}$  are respectively computed in Hardy and Wright as 

{\begin{aligned}\sum _{n\leq x}\omega (n)&=x\log \log x+B_{1}x+o(x)\\\sum _{n\leq x}\Omega (n)&=x\log \log x+B_{2}x+o(x)\\\sum _{n\leq x}\omega (n)^{2}&=x(\log \log x)^{2}+O(x\log \log x)\\\sum _{n\leq x}\omega (n)^{k}&=x(\log \log x)^{k}+O(x(\log \log x)^{k-1}),k\in \mathbb {Z} ^{+},\end{aligned}}

where $B_{1}$  is again the Mertens constant and the constant $B_{2}$  is defined by

$B_{2}=B_{1}+\sum _{p{\text{ prime}}}{\frac {1}{p(p-1)}}.$

Other sums relating the two variants of the prime omega functions include 

$\sum _{n\leq x}\left\{\Omega (n)-\omega (n)\right\}=O(x),$

and

$\#\left\{n\leq x:\Omega (n)-\omega (n)>{\sqrt {\log \log x}}\right\}=O\left({\frac {x}{(\log \log x)^{1/2}}}\right).$

### Example I: A modified summatory function

In this example we suggest a variant of the summatory functions $S_{\omega }(x):=\sum _{n\leq x}\omega (n)$  estimated in the above results for sufficiently large $x$ . We then prove an asymptotic formula for the growth of this modified summatory function derived from the asymptotic estimate of $S_{\omega }(x)$  provided in the formulas in the main subsection of this article above.

To be completely precise, let the odd-indexed summatory function be defined as

$S_{\operatorname {odd} }(x):=\sum _{n\leq x}\omega (n)[n{\text{ odd}}]_{\delta },$

where $[\cdot ]_{\delta }$  denotes Iverson's convention. Then we have that

$S_{\operatorname {odd} }(x)={\frac {x}{2}}\log \log x+{\frac {(2B_{1}-1)x}{4}}+\left\{{\frac {x}{4}}\right\}-\left[x\equiv 2,3{\bmod {4}}\right]_{\delta }+O\left({\frac {x}{\log x}}\right).$

The proof of this result follows by first observing that

$\omega (2n)={\begin{cases}\omega (n)+1,&{\text{if }}n{\text{ is odd; }}\\\omega (n),&{\text{if }}n{\text{ is even,}}\end{cases}}$

and then applying the asymptotic result from Hardy and Wright for the summatory function over $\omega (n)$ , denoted by $S_{\omega }(x):=\sum _{n\leq x}\omega (n)$ , in the following form:

{\begin{aligned}S_{\omega }(x)&=S_{\operatorname {odd} }(x)+\sum _{n\leq \left\lfloor {\frac {x}{2}}\right\rfloor }\omega (2n)\\&=S_{\operatorname {odd} }(x)+\sum _{n\leq \left\lfloor {\frac {x}{4}}\right\rfloor }\left(\omega (4n)+\omega (4n+2)\right)\\&=S_{\operatorname {odd} }(x)+\sum _{n\leq \left\lfloor {\frac {x}{4}}\right\rfloor }\left(\omega (2n)+\omega (2n+1)+1\right)\\&=S_{\operatorname {odd} }(x)+S_{\omega }\left(\left\lfloor {\frac {x}{2}}\right\rfloor \right)+\left\lfloor {\frac {x}{4}}\right\rfloor .\end{aligned}}

### Example II: Summatory functions for so-termed factorial moments of $\omega (n)$ The computations expanded in Chapter 22.11 of Hardy and Wright provide asymptotic estimates for the summatory function

$\omega (n)\left\{\omega (n)-1\right\},$

by estimating the product of these two component omega functions as

$\omega (n)\left\{\omega (n)-1\right\}=\sum _{\stackrel {pq\mid n}{\stackrel {p\neq q}{p,q{\text{ prime}}}}}1=\sum _{\stackrel {pq\mid n}{p,q{\text{ prime}}}}1-\sum _{\stackrel {p^{2}\mid n}{p{\text{ prime}}}}1.$

We can similarly calculate asymptotic formulas more generally for the related summatory functions over so-termed factorial moments of the function $\omega (n)$ .

## Dirichlet series

A known Dirichlet series involving $\omega (n)$  and the Riemann zeta function is given by 

$\sum _{n\geq 1}{\frac {2^{\omega (n)}}{n^{s}}}={\frac {\zeta ^{2}(s)}{\zeta (2s)}},\ \Re (s)>1.$

The function $\Omega (n)$  is completely additive, where $\omega (n)$  is strongly additive (additive). Now we can prove a short lemma in the following form which implies exact formulas for the expansions of the Dirichlet series over both $\omega (n)$  and $\Omega (n)$ :

Lemma. Suppose that $f$  is a strongly additive arithmetic function defined such that its values at prime powers is given by $f(p^{\alpha }):=f_{0}(p,\alpha )$ , i.e., $f(p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}})=f_{0}(p_{1},\alpha _{1})+\cdots +f_{0}(p_{k},\alpha _{k})$  for distinct primes $p_{i}$  and exponents $\alpha _{i}\geq 1$ . The Dirichlet series of $f$  is expanded by

$\sum _{n\geq 1}{\frac {f(n)}{n^{s}}}=\zeta (s)\times \sum _{p\mathrm {\ prime} }(1-p^{-s})\cdot \sum _{n\geq 1}f_{0}(p,n)p^{-ns},\Re (s)>\min(1,\sigma _{f}).$

Proof. We can see that

$\sum _{n\geq 1}{\frac {u^{f(n)}}{n^{s}}}=\prod _{p\mathrm {\ prime} }\left(1+\sum _{n\geq 1}u^{f_{0}(p,n)}p^{-ns}\right).$

This implies that

{\begin{aligned}\sum _{n\geq 1}{\frac {f(n)}{n^{s}}}&={\frac {d}{du}}\left[\prod _{p\mathrm {\ prime} }\left(1+\sum _{n\geq 1}u^{f_{0}(p,n)}p^{-ns}\right)\right]{\Biggr |}_{u=1}=\prod _{p}\left(1+\sum _{n\geq 1}p^{-ns}\right)\times \sum _{p}{\frac {\sum _{n\geq 1}f_{0}(p,n)p^{-ns}}{1+\sum _{n\geq 1}p^{-ns}}}\\&=\zeta (s)\times \sum _{p\mathrm {\ prime} }(1-p^{-s})\cdot \sum _{n\geq 1}f_{0}(p,n)p^{-ns},\end{aligned}}

wherever the corresponding series and products are convergent. In the last equation, we have used the Euler product representation of the Riemann zeta function. $\boxdot$

The lemma implies that for $\Re (s)>1$ ,

{\begin{aligned}D_{\omega }(s)&:=\sum _{n\geq 1}{\frac {\omega (n)}{n^{s}}}=\zeta (s)P(s)\\&\ =\zeta (s)\times \sum _{n\geq 1}{\frac {\mu (n)}{n}}\log \zeta (ns)\\D_{\Omega }(s)&:=\sum _{n\geq 1}{\frac {\Omega (n)}{n^{s}}}=\zeta (s)\times \sum _{n\geq 1}P(ns)\\&\ =\zeta (s)\times \sum _{n\geq 1}{\frac {\phi (n)}{n}}\log \zeta (ns)\\D_{\Omega \lambda }(s)&:=\sum _{n\geq 1}{\frac {\lambda (n)\Omega (n)}{n^{s}}}=\zeta (s)\log \zeta (s),\end{aligned}}

where $P(s)$  is the prime zeta function and $\lambda (n)=(-1)^{\Omega (n)}$  is the Liouville lambda function.

## The distribution of the difference of prime omega functions

The distribution of the distinct integer values of the differences $\Omega (n)-\omega (n)$  is regular in comparison with the semi-random properties of the component functions. For $k\geq 0$ , let the sets

$N_{k}(x):=\#\{n\leq x:\Omega (n)-\omega (n)=k\}.$

These sets have a corresponding sequence of limiting densities $d_{k}$  such that for $x\geq 2$

$N_{k}(x)=d_{k}\cdot x+O\left(\left({\frac {3}{4}}\right)^{k}{\sqrt {x}}(\log x)^{\frac {4}{3}}\right).$

These densities are generated by the prime products

$\sum _{k\geq 0}d_{k}\cdot z^{k}=\prod _{p}\left(1-{\frac {1}{p}}\right)\left(1+{\frac {1}{p-z}}\right).$

With the absolute constant ${\hat {c}}:={\frac {1}{4}}\times \prod _{p>2}\left(1-{\frac {1}{(p-1)^{2}}}\right)^{-1}$ , the densities $d_{k}$  satisfy

$d_{k}={\hat {c}}\cdot 2^{-k}+O(5^{-k}).$

Compare to the definition of the prime products defined in the last section of  in relation to the Erdős–Kac theorem.