This site is supported by donations to The OEIS Foundation.
Omega(n), number of prime factors of n (with multiplicity)
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 .
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).
Contents
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
- 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)
Notes
- ↑ 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
- Weisstein, Eric W., Sum of Prime Factors, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/SumofPrimeFactors.html]