xviii Frequently Used Functions

γ(n) =

p|n

p, the product of the prime numbers dividing n

φ(n) =

m≤n

(m,n)=1

1, the Euler φ function

σ(n) =

d|n

d, the sum of the (positive) divisors of n

σk(n) =

d|n

dk,

the sum of the k-th powers of the divisors of n

d(n) =

d|n

1, the number of divisors of n

ω(n) =

p|n

1, the number of distinct prime divisors of n

Ω(n) =

pα n

α, the number of prime factors of n counting multiplicity

Πk(x) =

n≤x

ω(n)=k

1, the number of integers n ≤ x such that ω(n) = k

μ(n), the M¨ obius function, defined by

μ(n) =

⎧

⎨

⎩

1 if n = 1,

0

p2|n

for some prime p,

(−1)ω(n)

otherwise.

λ(n) =

log n

log γ(n)

, the index of composition of the integer n ≥ 2