In number theory, the prime omega functions 👁 {\displaystyle \omega (n)}
and 👁 {\displaystyle \Omega (n)}
count the number of prime factors of a natural number 👁 {\displaystyle n}
. The number of distinct prime factors is assigned to 👁 {\displaystyle \omega (n)}
(little omega), while 👁 {\displaystyle \Omega (n)}
(big omega) counts the total number of prime factors with multiplicity (see arithmetic function). That is, if we have a prime factorization of 👁 {\displaystyle n}
of the form 👁 {\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}
for distinct primes 👁 {\displaystyle p_{i}}
(👁 {\displaystyle 1\leq i\leq k}
), then the prime omega functions are given by 👁 {\displaystyle \omega (n)=k}
and 👁 {\displaystyle \Omega (n)=\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}}
. These prime-factor-counting functions have many important number theoretic relations.

The function 👁 {\displaystyle \omega (n)}
is additive and 👁 {\displaystyle \Omega (n)}
is completely additive. Little omega has the formula

👁 {\displaystyle \omega (n)=\sum _{p\mid n}1,}

where notation p|n indicates that the sum is taken over all primes p that divide n, without multiplicity. For example, 👁 {\displaystyle \omega (12)=\omega (2^{2}3)=2}
.

Big omega has the formulas

👁 {\displaystyle \Omega (n)=\sum _{p^{\alpha }\mid n}1=\sum _{p^{\alpha }\parallel n}\alpha .}

The notation p^α|n indicates that the sum is taken over all prime powers p^α that divide n, while p^α||n indicates that the sum is taken over all prime powers p^α that divide n and such that n / p^α is coprime to p^α. For example, 👁 {\displaystyle \Omega (12)=\Omega (2^{2}3^{1})=3}
.

The omegas are related by the inequalities ω(n) ≤ Ω(n) and 2^ω(n) ≤ d(n) ≤ 2^Ω(n), where d(n) is the divisor-counting function.^[1] If Ω(n) = ω(n), then n is squarefree and related to the Möbius function by

👁 {\displaystyle \mu (n)=(-1)^{\omega (n)}=(-1)^{\Omega (n)}.}

If 👁 {\displaystyle \omega (n)=1}
then 👁 {\displaystyle n}
is a prime power, and if 👁 {\displaystyle \Omega (n)=1}
then 👁 {\displaystyle n}
is prime.

An asymptotic series for the average order of 👁 {\displaystyle \omega (n)}
is ^[2]

👁 {\displaystyle {\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 👁 {\displaystyle B_{1}\approx 0.26149721}
is the Mertens constant and 👁 {\displaystyle \gamma _{j}}
are the Stieltjes constants.

The function 👁 {\displaystyle \omega (n)}
is related to divisor sums over the Möbius function and the divisor function, including:^[3]

👁 {\displaystyle \sum _{d\mid n}|\mu (d)|=2^{\omega (n)}}
is the number of unitary divisors. (sequence A034444 in the OEIS)

👁 {\displaystyle \sum _{d\mid n}|\mu (d)|k^{\omega (d)}=(k+1)^{\omega (n)}}

👁 {\displaystyle \sum _{r\mid n}2^{\omega (r)}=d(n^{2})}

👁 {\displaystyle \sum _{r\mid n}2^{\omega (r)}d\left({\frac {n}{r}}\right)=d^{2}(n)}

👁 {\displaystyle \sum _{d\mid n}(-1)^{\omega (d)}=\prod \limits _{p^{\alpha }||n}(1-\alpha )}

👁 {\displaystyle \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})}

👁 {\displaystyle \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:^[4]

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

A partition-related exact identity for 👁 {\displaystyle \omega (n)}
is given by ^[5]

👁 {\displaystyle \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 👁 {\displaystyle p(n)}
is the partition function, 👁 {\displaystyle \mu (n)}
is the Möbius function, and the triangular sequence 👁 {\displaystyle s_{n,k}}
is expanded by

👁 {\displaystyle 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 👁 {\displaystyle s_{o/e}(n,k)}
which respectively denote the number of 👁 {\displaystyle k}
's in all partitions of 👁 {\displaystyle n}
into an odd (even) number of distinct parts.^[6]

A continuation of 👁 {\displaystyle \omega (n)}
has been found, though it is not analytic everywhere.^[7] Note that the normalized 👁 {\displaystyle \operatorname {sinc} }
function 👁 {\displaystyle \operatorname {sinc} (x)={\frac {\sin(\pi x)}{\pi x}}}
is used.

👁 {\displaystyle \omega (z)=\log _{2}\left(\sum _{n=1}^{\lceil Re(z)\rceil }\operatorname {sinc} \left(\prod _{m=1}^{\lceil Re(z)\rceil +1}\left(n^{2}+n-mz\right)\right)\right)}

This is closely related to the following partition identity. Consider partitions of the form

👁 {\displaystyle a={\frac {2}{c}}+{\frac {4}{c}}+\ldots +{\frac {2(b-1)}{c}}+{\frac {2b}{c}}}

where 👁 {\displaystyle a}
, 👁 {\displaystyle b}
, and 👁 {\displaystyle c}
are positive integers, and 👁 {\displaystyle a>b>c}
. The number of partitions is then given by 👁 {\displaystyle 2^{\omega (a)}-2}
. ^[8]

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

👁 {\displaystyle \omega (n)\sim {\frac {\log n}{\log \log n}}}

on average order. When 👁 {\displaystyle n}
is a power of 2, then 👁 {\displaystyle \Omega (n)=\log _{2}(n).}
^[9]

Asymptotics for the summatory functions over 👁 {\displaystyle \omega (n)}
, 👁 {\displaystyle \Omega (n)}
, and powers of 👁 {\displaystyle \omega (n)}
are respectively^[10][11]

👁 {\displaystyle {\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 👁 {\displaystyle B_{1}\approx 0.2614972128}
is the Mertens constant and the constant 👁 {\displaystyle B_{2}}
is defined by

👁 {\displaystyle B_{2}=B_{1}+\sum _{p{\text{ prime}}}{\frac {1}{p(p-1)}}\approx 1.0345061758.}

The sum of number of unitary divisors is

👁 {\displaystyle \sum _{n\leq x}2^{\omega (n)}=(x\log x)/\zeta (2)+O(x)}
^[12] (sequence A064608 in the OEIS)

Other sums relating the two variants of the prime omega functions include ^[13]

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

and

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

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

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

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

where 👁 {\displaystyle [\cdot ]}
denotes Iverson bracket. Then we have that

👁 {\displaystyle 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]+O\left({\frac {x}{\log x}}\right).}

The proof of this result follows by first observing that

👁 {\displaystyle \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 👁 {\displaystyle \omega (n)}
, denoted by 👁 {\displaystyle S_{\omega }(x):=\sum _{n\leq x}\omega (n)}
, in the following form:

👁 {\displaystyle {\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}}}

The computations expanded in Chapter 22.11 of Hardy and Wright provide asymptotic estimates for the summatory function

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

by estimating the product of these two component omega functions as

👁 {\displaystyle \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 👁 {\displaystyle \omega (n)}
.

A known Dirichlet series involving 👁 {\displaystyle \omega (n)}
and the Riemann zeta function is given by ^[15]

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

We can also see that

👁 {\displaystyle \sum _{n\geq 1}{\frac {z^{\omega (n)}}{n^{s}}}=\prod _{p}\left(1+{\frac {z}{p^{s}-1}}\right),|z|<2,\Re (s)>1,}

👁 {\displaystyle \sum _{n\geq 1}{\frac {z^{\Omega (n)}}{n^{s}}}=\prod _{p}\left(1-{\frac {z}{p^{s}}}\right)^{-1},|z|<2,\Re (s)>1,}

The function 👁 {\displaystyle \Omega (n)}
is completely additive, where 👁 {\displaystyle \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 👁 {\displaystyle \omega (n)}
and 👁 {\displaystyle \Omega (n)}
:

Lemma. Suppose that 👁 {\displaystyle f}
is a strongly additive arithmetic function defined such that its values at prime powers is given by 👁 {\displaystyle f(p^{\alpha }):=f_{0}(p,\alpha )}
, i.e., 👁 {\displaystyle 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 👁 {\displaystyle p_{i}}
and exponents 👁 {\displaystyle \alpha _{i}\geq 1}
. The Dirichlet series of 👁 {\displaystyle f}
is expanded by

👁 {\displaystyle \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

👁 {\displaystyle \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

👁 {\displaystyle {\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.

The lemma implies that for 👁 {\displaystyle \Re (s)>1}
,

👁 {\displaystyle {\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_{h}(s)&:=\sum _{n\geq 1}{\frac {h(n)}{n^{s}}}=\zeta (s)\log \zeta (s)\\&\ =\zeta (s)\times \sum _{n\geq 1}{\frac {\varepsilon (n)}{n}}\log \zeta (ns),\end{aligned}}}

where 👁 {\displaystyle P(s)}
is the prime zeta function, 👁 {\displaystyle h(n)=\sum _{p^{k}|n}{\frac {1}{k}}=\sum _{p^{k}||n}{H_{k}}}
where 👁 {\displaystyle H_{k}}
is the 👁 {\displaystyle k}
-th harmonic number and 👁 {\displaystyle \varepsilon }
is the identity for the Dirichlet convolution, 👁 {\displaystyle \varepsilon (n)=\lfloor {\frac {1}{n}}\rfloor }
.

The distribution of the distinct integer values of the differences 👁 {\displaystyle \Omega (n)-\omega (n)}
is regular in comparison with the semi-random properties of the component functions. For 👁 {\displaystyle k\geq 0}
, define

👁 {\displaystyle N_{k}(x):=\#(\{n\in \mathbb {Z} ^{+}:\Omega (n)-\omega (n)=k\}\cap [1,x]).}

These cardinalities have a corresponding sequence of limiting densities 👁 {\displaystyle d_{k}}
such that for 👁 {\displaystyle x\geq 2}

👁 {\displaystyle 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

👁 {\displaystyle \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 👁 {\displaystyle {\hat {c}}:={\frac {1}{4}}\times \prod _{p>2}\left(1-{\frac {1}{(p-1)^{2}}}\right)^{-1}}
, the densities 👁 {\displaystyle d_{k}}
satisfy

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

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

• Additive function
• Arithmetic function
• Erdős–Kac theorem
• Omega function (disambiguation)
• Prime number
• Square-free integer

• G. H. Hardy and E. M. Wright (2006). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.
• H. L. Montgomery and R. C. Vaughan (2007). Multiplicative number theory I. Classical theory (1st ed.). Cambridge University Press.
• Schmidt, Maxie (2017). "Factorization Theorems for Hadamard Products and Higher-Order Derivatives of Lambert Series Generating Functions". arXiv:1712.00608 [math.NT].
• Weisstein, Eric. "Distinct Prime Factors". MathWorld. Retrieved 22 April 2018.

• OEIS Wiki for related sequence numbers and tables
• OEIS Wiki on Prime Factors

Retrieved from "https://en.wikipedia.org/w/index.php?title=Prime_omega_function&oldid=1321250987"