This site is supported by donations to The OEIS Foundation.

Number of divisors function

From OeisWiki
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


The divisor function
σk (n)
for a positive integer
n
is defined as the sum of the 
k
th powers of the divisors of 
n
For 
k = 0
we get
where 
τ (n)
is the number of divisors function. The notations 
d (n)
[1], 
ν (n)
[2], and 
τ (n)
[3] are sometimes used for 
σ0(n)
, which gives the number of divisors of 
n
. For 
n   ≥   1
, the number of divisors is the number of restricted partitions with parts of equal size.

A000005
d (n)
(also called 
τ (n)
or 
σ0(n)
), the number of divisors of 
n, n   ≥   1
.
{1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, ...}

Number of divisors greater than 1, number of divisors smaller than n

The number of divisors greater than 1 (same as number of aliquot divisors, i.e. number of divisors smaller than n) of 
n
is one less than the number of divisors of 
n
.

Formulae for the number of divisors function

From the prime factorization of 
n
where the 
pi
are the distinct prime factors of 
n
and 
ω (n)
is the number of distinct prime factors of 
n
, we obtain the number of divisors of 
n
since for each 
pi
we can choose the exponent from 
0
to 
αi
to build a divisor of 
n
.[4]

Generating function of number of divisors function

The generating function is

This is usually called THE Lambert series (see Knopp, Titchmarsh).

Dirichlet generating function of number of divisors function

The Dirichlet generating function is

Number of ways of factoring n with all factors greater than 1

What is the relation between the number of ways of factoring n with all factors greater than 1 and the number of divisors greater than 1 (same as number of aliquot divisors) of 
n
?

Number of even divisors

(...)

Number of odd divisors

(...)

Number of divisors of form 4m + 1

(...)

Number of divisors of form 4m + 3

(...)

(number of divisors of form 4m + 1) − (number of divisors of form 4m + 3)

A002654 Number of ways of writing 
n
as a sum of at most two nonzero squares, where order matters; also (number of divisors of 
n
of form 
4 m + 1
) 
 − 
(number of divisors of 
n
of form 
4 m + 3
).
{1, 1, 0, 1, 2, 0, 0, 1, 1, 2, 0, 0, 2, 0, 0, 1, 2, 1, 0, 2, 0, 0, 0, 0, 3, 2, 0, 0, 2, 0, 0, 1, 0, 2, 0, 1, 2, 0, 0, 2, 2, 0, 0, 0, 2, 0, 0, 0, 1, 3, 0, 2, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 4, 0, 0, 2, 0, 0, 0, 1, ...}

A213408 Sequence A002654 with the zero terms omitted.

{1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 3, 2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 1, 4, 2, 1, 2, 2, 2, 1, 2, 4, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 2, 1, 2, 4, 1, 4, 2, 2, 1, 4, 2, 2, 2, 2, 2, 2, 1, 2, 3, 4, 2, 2, 2, ...}

See also



Arithmetic function templates

Notes

  1. Hardy and Wright 1979, p. 239.
  2. Ore 1988, p. 86.
  3. Burton 1989, p. 128.
  4. Charles Vanden Eynden, Elementary Number Theory, 2nd Edition. Long Grove, Illinois: Waveland Press (2001): 71

References

  • Burton, D. M. (1989). Elementary Number Theory (4th ed.). Boston, MA: Allyn and Bacon. 
  • Hardy, G. H.; Wright, E. M. (1979). An Introduction to the Theory of Numbers (5th ed.). Oxford, England: Oxford University Press. pp. 354-355. 
  • Ore, Ø. (1988). Number Theory and Its History. New York: Dover.