Omega(n), number of prime factors of n (with multiplicity)

This article needs more work.

Please help by expanding it!

The function $\scriptstyle \Omega (n)\,$ counts the number of prime factors of n (with multiplicity), where $\scriptstyle n\,$ is a positive integer, each distinct prime factor of n being counted as many times as the number of its positive powers that divide $\scriptstyle n\,$.

From the canonical prime factorization of $\scriptstyle n\,$

$n=\prod _{i=1}^{\omega (n)}{p_{i}}^{\alpha _{i}},\,$

where $\scriptstyle \omega (n)\,$ is the number of distinct prime factors of n and each $\scriptstyle \alpha _{i}\,=\,\nu _{p_{i}}(n)\,$, where $\scriptstyle \nu _{p_{i}}(n)\,$ is the $\scriptstyle p_{i}\,$-adic order of $\scriptstyle n\,$, we have

$\Omega (n)\equiv \sum _{i=1}^{\omega (n)}{\alpha _{i}}=\sum _{i=1}^{\omega (n)}{\nu _{p_{i}}(n)}=\sum _{{p\mid n} \atop {p~{\rm {prime}}}}\nu _{p}(n),\,$

where $\scriptstyle \nu _{p}(n)\,$ is the p-adic order of $\scriptstyle n\,$, i.e. the highest exponent $\scriptstyle \nu \,$ of prime number $\scriptstyle p\,$ such that $\scriptstyle p^{\nu }\,$ divides $\scriptstyle n\,$.

For example, for $\scriptstyle n\,=\,44100\,=\,(3\cdot 7)^{2}\cdot (2\cdot 5)^{2}\,=\,2^{2}3^{2}5^{2}7^{2}\,$ we have $\scriptstyle \Omega (44100)\,=\,\Omega (2^{2}3^{2}5^{2}7^{2})\,=\,8\,$, as the eight prime factors (with repetition) of $\scriptstyle n\,$ are 2, 2, 3, 3, 5, 5, 7, and 7.

Obviously $\scriptstyle \Omega (1)\,=\,0\,$ since 1 is the product of no primes, and for $\scriptstyle p\,$ prime we have $\scriptstyle \Omega (p)\,=\,1\,$ since a prime has only one prime factor (itself).

Formulae

Algebraically, we can define $\scriptstyle \Omega (n)\,$ for composite $\scriptstyle n\,$ as

$\Omega (n)=\sum _{i=1}^{\pi (\lfloor {\sqrt {n}}\rfloor )}\sum _{j=1}^{\lfloor \log _{p_{i}}n\rfloor }[{p_{i}}^{j}|n],\,$

or somewhat more efficiently, using short-circuit evaluation to avoid calculating $\scriptstyle \log _{p_{i}}n\,$ unnecessarily, as

$\Omega (n)=\sum _{i=1}^{\pi (\lfloor {\sqrt {n}}\rfloor )}[p_{i}|n]{\Bigg (}1+\sum _{j=2}^{\lfloor \log _{p_{i}}n\rfloor }[{p_{i}}^{j}|n]{\Bigg )},\,$

where $\scriptstyle \pi (n)\,$ is the prime counting function, $\scriptstyle [\cdot ]\,$ is the Iverson bracket, $\scriptstyle p_{i}\,$ is the $\scriptstyle i\,$^th prime. But of course it is far more efficient to compute the prime factorization of $\scriptstyle n\,$ and then from that determine the value of $\scriptstyle \Omega (n)\,$.

Properties

$\scriptstyle \Omega (n)\,$ is a completely additive arithmetic function, i.e.

$\Omega (mn)=\Omega (m)+\Omega (n),\ m\,\geq \,1,\ n\,\geq \,1.\,$

If $\scriptstyle n\,$ is a squarefree number, then $\scriptstyle \Omega (n)\,=\,\omega (n)\,$, otherwise $\scriptstyle \Omega (n)\,>\,\omega (n)\,$ (hence the capital letter for the number of prime factors (with repetition) function and the lowercase letter for the number of distinct prime factors function).

Related arithmetic functions

Liouville's function

Liouville's function, expressing the parity of $\scriptstyle \Omega (n)\,$,

$\lambda (n)\equiv (-1)^{\Omega (n)}\,$

is +1 when $\scriptstyle \Omega (n)\,$ is even and -1 when $\scriptstyle \Omega (n)\,$ is odd.

Excess of n

$\scriptstyle \Omega (n)\,-\,\omega (n),\ n\,\geq \,1,\,$ excess of n = number of prime factors of n (with multiplicity) - number of prime factors of n (without multiplicity). (See A046660.)

{0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 3, 0, 1, 0, 1, 0, 0, 0, 2, 1, 0, 2, 1, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, 3, 1, 1, 0, 1, 0, 2, 0, 2, 0, 0, 0, 1, 0, 0, 1, 5, 0, 0, 0, ...}

Characteristic function of nonsquarefree numbers

The complement $\scriptstyle {\bar {q}}(n)\,=\,1\,-\,q(n)\,$ of the quadratfrei function $\scriptstyle q(n)\,$, $\scriptstyle {\bar {q}}(n)\,\equiv \,\chi _{\{nonsquarefree\}}(n)\,\equiv \,\operatorname {sgn}[\Omega (n)\,-\,\omega (n)],\ n\,\geq \,1,\,$ is the characteristic function of nonsquarefree numbers, $\scriptstyle \operatorname {sgn}(n)\,$ being the sign function.

Characteristic function of squarefree numbers

The quadratfrei function $\scriptstyle q(n)\,\equiv \,1\,-\,{\bar {q}}(n)\,\equiv \,\chi _{\{squarefree\}}(n)\,\equiv \,1\,-\,\operatorname {sgn}[\Omega (n)\,-\,\omega (n)],\ n\,\geq \,1\,$ is the characteristic function of squarefree numbers, $\scriptstyle \operatorname {sgn}(n)\,$ being the sign function.

Sequences

$\scriptstyle \Omega (n),\ n\,\geq \,1,\,$ Omega(n), number of prime factors of n (with multiplicity). (See A001222.)

{0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, ...}

$\scriptstyle \sum _{i=1}^{n}\Omega (i),\ n\,\geq \,1,\,$ summatory Omega function, number of prime factors of n! (with multiplicity). (See A022559$\scriptstyle (n),\,n\,\geq \,1\,$.)

{0, 1, 2, 4, 5, 7, 8, 11, 13, 15, 16, 19, 20, 22, 24, 28, 29, 32, 33, 36, 38, 40, 41, 45, 47, 49, 52, 55, 56, 59, 60, 65, 67, 69, 71, 75, 76, 78, 80, 84, 85, 88, 89, 92, 95, ...}

Liouville's function $\scriptstyle \lambda (n)\,\equiv \,(-1)^{\Omega (n)},\ n\,\geq \,1\,$. (See A008836.)

{1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, ...}

The partial sums $\scriptstyle L(n)\,\equiv \,\sum _{i=1}^{n}\lambda (i)\,=\,\sum _{i=1}^{n}(-1)^{\Omega (i)},\ n\,\geq \,1,\,$ summatory Liouville function. (See A002819 for $\scriptstyle n\,\geq \,1\,$.)

{1, 0, -1, 0, -1, 0, -1, -2, -1, 0, -1, -2, -3, -2, -1, 0, -1, -2, -3, -4, -3, -2, -3, -2, -1, 0, -1, -2, -3, -4, -5, -6, -5, -4, -3, -2, -3, -2, -1, 0, -1, -2, -3, -4, -5, -4, -5, -6, -5, -6, -5, -6, -7, -6, -5, ...}

$\scriptstyle \omega (n),\ n\,\geq \,1,\,$ number of prime factors of n (without multiplicity), number of distinct prime factors of n. (See A001221.)

{0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, ...}

$\scriptstyle {\bar {q}}(n)\,\equiv \,\chi _{\{nonsquarefree\}}(n)\,\equiv \,\operatorname {sgn}[\Omega (n)\,-\,\omega (n)],\ n\,\geq \,1,\,$ (0, or 1 if n has nonunitary prime divisors,) nonquadratfrei function, characteristic function of nonsquarefree numbers. (See A107078.)

{0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, ...}

$\scriptstyle q(n)\,\equiv \,1\,-\,{\bar {q}}(n)\,\equiv \,\chi _{\{squarefree\}}(n)\,\equiv \,1\,-\,\operatorname {sgn}[\Omega (n)\,-\,\omega (n)],\ n\,\geq \,1,\,$ (0, or 1 if n has unitary prime divisors only,) quadratfrei function, characteristic function of squarefree numbers. (See A008966.)

{1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...}

See also

• Distinct prime factors of n or prime factors of n (without multiplicity)
  • {{Distinct prime factors}} or {{dpf}} arithmetic function template
• Number of distinct prime factors of n or number of prime factors of n (without multiplicity) (omega(n))
  • {{Number of distinct prime factors}} or {{little omega}} arithmetic function template
• Sum of distinct prime factors of n (sopf(n))
  • {{Sum of distinct prime factors}} or {{sopf}} (sum of prime factors) arithmetic function template
• Product of distinct prime factors of n (rad(n), the radical or squarefree kernel of n)
  • {{Product of distinct prime factors}} or {{rad}} arithmetic function template

• Prime factors of n (with multiplicity)
  • {{Prime factors (with multiplicity)}} or {{mpf}} arithmetic function template
• Number of prime factors of n (with multiplicity) (Omega(n))
  • {{Number of prime factors (with multiplicity)}} or {{big Omega}} arithmetic function template
• Sum of prime factors of n (with multiplicity) (sopfr(n))
  • {{Sum of prime factors (with multiplicity)}} or {{sopfr}} (sum of prime factors with repetition) arithmetic function template
• Product of prime factors of n (with multiplicity) (positive integers)

External links

• Weisstein, Eric W., Sum of Prime Factors, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/SumofPrimeFactors.html]