This site is supported by donations to The OEIS Foundation.

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

From OeisWiki
(Redirected from Number of prime factors of n (with multiplicity))
Jump to: navigation, search

This article needs more work.

Please help by expanding it!


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

From the canonical prime factorization of

where is the number of distinct prime factors of n and each , where is the -adic order of , we have

where is the p-adic order of , i.e. the highest exponent of prime number such that divides .

A001222.png

For example, for we have , as the eight prime factors (with repetition) of are 2, 2, 3, 3, 5, 5, 7, and 7.

Obviously since 1 is the product of no primes, and for prime we have since a prime has only one prime factor (itself).

Formulae

Algebraically, we can define for composite as

or somewhat more efficiently, using short-circuit evaluation to avoid calculating unnecessarily, as

where is the prime counting function, is the Iverson bracket, is the th prime. But of course it is far more efficient to compute the prime factorization of and then from that determine the value of .

Properties

is a completely additive arithmetic function, i.e.

If is a squarefree number, then , otherwise (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 ,

is +1 when is even and -1 when is odd.

Excess of n

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 of the quadratfrei function , is the characteristic function of nonsquarefree numbers, being the sign function.

Characteristic function of squarefree numbers

The quadratfrei function is the characteristic function of squarefree numbers, being the sign function.

Sequences

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, ...}

summatory Omega function, number of prime factors of n! (with multiplicity). (See A022559.)

{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 . (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 summatory Liouville function. (See A002819 for .)

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

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, ...}

(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, ...}

(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


Notes

  1. Mathematica uses for the latter. Only in the documentation for PrimeNu have I seen this usage. is of course in that program implemented as PrimeOmega[n].

External links