This site is supported by donations to The OEIS Foundation.

# Omega(n), number of distinct primes dividing n

(Redirected from Number of distinct prime factors of n)

The canonical prime factorization of
 n
being
$n = \prod_{i=1}^{\omega(n)} {p_i}^{\alpha_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.
$\omega(mn) = \omega(m) + \omega(n),\ m \,\ge\, 1,\quad n \,\ge\, 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^{\omega(n)}\}}(s) \equiv \sum_{n=1}^{\infty} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta^2(s)}{\zeta(2s)},\ 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 $\scriptstyle \omega(n)\,$, (Liouville's function being $\scriptstyle \lambda(n) \,\equiv\, {\lambda}_{\Omega}(n) \,\equiv\, (-1)^{\Omega(n)}\,$ for $\scriptstyle \Omega(n)\,$, the total number of primes dividing n)

${\lambda}_{\omega}(n) \equiv (-1)^{\omega(n)}\,$
is +1 when
 ω (n)
is even and -1 when
 ω (n)
is odd.

### Excess of n

A046660 $\scriptstyle \Omega(n) \,-\, \omega(n),\ n \,\ge\, 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 $\scriptstyle \bar{q}(n) \,=\, 1 \,-\, q(n)\,$ of the quadratfrei function $\scriptstyle q(n)\,$, $\scriptstyle \bar{q}(n) \,\equiv\, \chi_{\{nonsquarefree\}}(n) \,\equiv\, \sgn [\Omega(n) \,-\, \omega(n)],\ n \,\ge\, 1,\,$ is the characteristic function of nonsquarefree numbers, $\scriptstyle \sgn(n)\,$ being the sign function.

#### Characteristic function of squarefree numbers

The quadratfrei function $\scriptstyle q(n) \,\equiv\, 1 \,-\, \bar{q}(n) \,\equiv\, \chi_{\{squarefree\}}(n) \,\equiv\, 1 \,-\, \sgn [\Omega(n) \,-\, \omega(n)],\ n \,\ge\, 1\,$ is the characteristic function of squarefree numbers, $\scriptstyle \sgn(n)\,$ being the sign function.

## Sequences

A001221 $\scriptstyle \omega(n),\ n \,\ge\, 1,\,$ 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 $\scriptstyle \sum_{i=1}^{n} \omega(i),\ n \,\ge\, 1, \,$ 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?????? $\scriptstyle {\lambda}_{\omega}(n) \,\equiv\, (-1)^{\omega(n)},\ n \,\ge\, 1, \,$ "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 $\scriptstyle L_{\omega}(n) \,\equiv\, \sum_{i=1}^{n} {\lambda}_{\omega}(i) \,\equiv\, \sum_{i=1}^{n} (-1)^{\omega(i)},\ n \,\ge\, 1, \,$ "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 $\scriptstyle \Omega(n),\ n \,\ge\, 1, \,$ 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 $\scriptstyle \bar{q}(n) \,\equiv\, \chi_{\{nonsquarefree\}}(n) \,\equiv\, \sgn [\Omega(n) \,-\, \omega(n)],\ n \,\ge\, 1, \,$ (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 $\scriptstyle q(n) \,\equiv\, 1 \,-\, \bar{q}(n) \,\equiv\, \chi_{\{squarefree\}}(n) \,\equiv\, 1 \,-\, \sgn [\Omega(n) \,-\, \omega(n)],\ n \,\ge\, 1, \,$ (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, ...}