This site is supported by donations to The OEIS Foundation.

Omega(n), number of distinct primes dividing n

(Redirected from Omega(n), number of distinct prime factors of n)

The canonical prime factorization of
 n
being
n  =
 ω (n) ∏ i   = 1

piαi ,
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.
 ω (m n)  =  ω (m) + ω (n), m ≥ 1, n ≥ 1, (m, n) = 1,
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
D{2ω (n)}(s)  :=
 ∞ ∑ n   = 1

 2 ω (n) n  s
=
 ζ  2 (s) ζ  (2 s)
, s > 1,
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
 ω (n)
, (Liouville’s function being
 λ (n)   :=   λ Ω (n)   :=   ( − 1) Ω (n)
for
 Ω (n)
, the number of prime factors of n (with multiplicity))
 λω (n)  :=  (−1) ω (n)
is +1 when
 ω (n)
is even and  − 1 when
 ω (n)
is odd.

Excess of n

A046660
 Ω (n)  −  ω (n), n   ≥   1,
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
 q̅  (n)   :=   1  −  q (n)
 q (n)
,
 q̅  (n)   :=   χnonsquarefree(n) = sgn [Ω (n)  −  ω (n)], n   ≥   1,
is the characteristic function of nonsquarefree numbers,
 sgn (n)
being the sign function.

Characteristic function of squarefree numbers

 q (n)   :=   1  −  q̅  (n)   :=   χsquarefree(n) = 1  −  sgn [Ω (n)  −  ω (n)], n   ≥   1,
is the characteristic function of squarefree numbers,
 sgn (n)
being the sign function.

Sequences

A001221 Number of prime factors of n (without multiplicity) (number of distinct prime factors of n):
 ω (n), n   ≥   1.
{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 Summatory ω function: partial sums
 n

 i   = 1
ω (i ), n   ≥   1.
{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”:
 λω (n)   :=   ( − 1) ω (n), 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, 1, –1, –1, –1, 1, 1, 1, –1, 1, –1, 1, 1, 1, –1, 1, 1, 1, 1, 1, –1, –1, ...}
A?????? “Summatory distinct primes version of Liouville’s function”: partial sums
Lω (n)   :=
 n

 i   = 1
λω (i ) =
 n

 i   = 1
( − 1)ω (i ), n   ≥   1.
{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):
 Ω (n), n   ≥   1.
{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 Nonquadratfrei function (characteristic function of nonsquarefree numbers):
 q̅  (n)   :=   1  −  q (n)   :=   χnonsquarefree(n) = sgn [Ω (n)  −  ω (n)], n   ≥   1.
(0, or 1 if n has nonunitary prime divisors.)
{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 Quadratfrei function (characteristic function of squarefree numbers):
 q (n)   :=   1  −  q̅  (n)   :=   χsquarefree(n) = 1  −  sgn [Ω (n)  −  ω (n)], n   ≥   1.
(0, or 1 if n has unitary prime divisors only.)
{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, ...}