This site is supported by donations to The OEIS Foundation.

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

The function ${\displaystyle \scriptstyle \Omega (n)\,}$ counts the number of prime factors of n (with multiplicity), where ${\displaystyle \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 ${\displaystyle \scriptstyle n\,}$.

From the canonical prime factorization of ${\displaystyle \scriptstyle n\,}$

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

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

${\displaystyle \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 ${\displaystyle \scriptstyle \nu _{p}(n)\,}$ is the p-adic order of ${\displaystyle \scriptstyle n\,}$, i.e. the highest exponent ${\displaystyle \scriptstyle \nu \,}$ of prime number ${\displaystyle \scriptstyle p\,}$ such that ${\displaystyle \scriptstyle p^{\nu }\,}$ divides ${\displaystyle \scriptstyle n\,}$.

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

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

## Formulae

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

${\displaystyle \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 ${\displaystyle \scriptstyle \log _{p_{i}}n\,}$ unnecessarily, as

${\displaystyle \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 ${\displaystyle \scriptstyle \pi (n)\,}$ is the prime counting function, ${\displaystyle \scriptstyle [\cdot ]\,}$ is the Iverson bracket, ${\displaystyle \scriptstyle p_{i}\,}$ is the ${\displaystyle \scriptstyle i\,}$th prime. But of course it is far more efficient to compute the prime factorization of ${\displaystyle \scriptstyle n\,}$ and then from that determine the value of ${\displaystyle \scriptstyle \Omega (n)\,}$.

## Properties

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

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

If ${\displaystyle \scriptstyle n\,}$ is a squarefree number, then ${\displaystyle \scriptstyle \Omega (n)\,=\,\omega (n)\,}$, otherwise ${\displaystyle \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).[1]

## Related arithmetic functions

### Liouville's function

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

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

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

### Excess of n

${\displaystyle \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 ${\displaystyle \scriptstyle {\bar {q}}(n)\,=\,1\,-\,q(n)\,}$ of the quadratfrei function ${\displaystyle \scriptstyle q(n)\,}$, ${\displaystyle \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, ${\displaystyle \scriptstyle \operatorname {sgn}(n)\,}$ being the sign function.

#### Characteristic function of squarefree numbers

The quadratfrei function ${\displaystyle \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, ${\displaystyle \scriptstyle \operatorname {sgn}(n)\,}$ being the sign function.

## Sequences

${\displaystyle \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, ...}

${\displaystyle \scriptstyle \sum _{i=1}^{n}\Omega (i),\ n\,\geq \,1,\,}$ summatory Omega function, number of prime factors of n! (with multiplicity). (See A022559${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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, ...}

${\displaystyle \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, ...}

${\displaystyle \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, ...}

${\displaystyle \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, ...}

1. Mathematica uses ${\displaystyle \scriptstyle \nu (n)\,}$ for the latter. Only in the documentation for PrimeNu have I seen this usage. ${\displaystyle \scriptstyle \Omega (n)\,}$ is of course in that program implemented as PrimeOmega[n].