Sunday, March 17, 2013

The big omega function

The big omega function (A001222) describes the number of prime divisors of a number counted with multiplicity: 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, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2.

The numbers zero and one do not have any prime factors. The prime numbers (A000040) have one factor, the semiprimes (A001358) have two factors, and the k-almost primes have k factors.

The big omega function tells us about the maximum number of fields of a structure of some cardinality. In practice, many structures don't use the prime factorization so they have even fewer fields then they do factors.

The number of multiplicative partitions of a number n with k factors is in the interval from p(k) to B(k) where p is the number of of additive partitions of k and B is the number of equivalence relations of size k