This site is supported by donations to The OEIS Foundation.

Omega(n), number of distinct primes dividing n

From OeisWiki
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


The canonical prime factorization of
n
being
where the function
ω (n)
is the number of distinct prime factors of the positive integer
n
, each prime factor being counted only once. For example, for
n = 44100 = (3 ⋅ 7) 2 (2 ⋅ 5) 2 = 2 2 3 2 5 2 7 2
we have
ω (44100) = ω (2 2 3 2 5 2 7 2) = 4
, as the four distinct primes factors of
n
are
2, 3, 5
and
7
.

For any positive value
k
, since
gcd (n, n + 1) = 1
and
gcd (n, n  −  1) = 1
, the following sequences give constructive proofs that there exists integers with at least
k
distinct prime factors.

A007018
a (0) = 1; a (n) = a (n  −  1) (a (n  −  1) + 1), n   ≥   1.
{1, 2, 6, 42, 1806, 3263442, 10650056950806, 113423713055421844361000442, 12864938683278671740537145998360961546653259485195806, ...}
A117805
a (0) = 3; a (n) = a (n  −  1) (a (n  −  1)  −  1), n   ≥   1.
{3, 6, 30, 870, 756030, 571580604870, 326704387862983487112030, 106735757048926752040856495274871386126283608870, ...}

Properties

ω (n)
is an additive arithmetic function, i.e.
where
(m, n)
is the greatest common divisor of
m
and
n
.

Dirichlet generating function

The Dirichlet generating function of
2ω (n), n   ≥   1,
is
where
ζ (s)
is the Riemann zeta function (Hardy and Wright 1979, p. 255).

Related arithmetic functions

Related arithmetic functions
n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
ω (n)
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
n

i  = 1
ω (i)
0 1 2 3 4 6 7 8 9 11 12 14 15 17 19 20 21 23 24 26 28 30 31 33 34 36 37 39 40 43 44 45 47 49 51 53 54 56 58 60
( − 1)ω (n)
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
n

i  = 1
 ( − 1)ω (i)
1 0 –1 –2 –3 –2 –3 –4 –5 –4 –5 –4 –5 –4 –3 –4 –5 –4 –5 –4 –3 –2 –3 –2 –3 –2 –3 –2 –3 –4 –5 –6 –5 –4 –3 –2 –3 –2 –1 0

"Distinct primes version of Liouville's function"

The "distinct primes version of Liouville's function", expressing the parity of , (Liouville's function being for , the total number of primes dividing n)

is +1 when
ω (n)
is even and -1 when
ω (n)
is odd.

Excess of n

A046660 excess of n = number of prime factors of n (with multiplicity) - number of prime factors of n (without multiplicity).

{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

A001221 number of prime factors of n (without multiplicity), number of distinct prime factors of n.

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

A013939 The partial sums summatory omega function.

{0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 17, 19, 20, 21, 23, 24, 26, 28, 30, 31, 33, 34, 36, 37, 39, 40, 43, 44, 45, 47, 49, 51, 53, 54, 56, 58, 60, 61, 64, 65, 67, 69, 71, 72, 74, 75, ...}

A?????? "distinct primes version of Liouville's function."

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

A?????? The partial sums "summatory distinct primes version of Liouville's function."

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

A001222 number of prime factors of n (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, ...}

A107078 (0, or 1 if n has nonunitary prime divisors), nonquadratfrei function, characteristic function of nonsquarefree numbers.

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

A008966 (0, or 1 if n has unitary prime divisors only), quadratfrei function, characteristic function of squarefree numbers.

{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

  • A056912 Odd squarefree numbers for which the number of prime divisors is odd.
  • A056913 Odd squarefree numbers for which the number of prime divisors is even.