This site is supported by donations to The OEIS Foundation.

Omega(n), number of distinct primes dividing n

From OeisWiki
(Redirected from Number of distinct prime factors function)
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


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.
ω (mn)  =  ω (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
  (n)   :=   1  −  q (n)
of the quadratfrei function
q (n)
,
  (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

The quadratfrei function
q (n)   :=   1  −    (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):
  (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  −    (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, ...}

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.