TOPICS
Search

Divisor Function


DivisorFunction

The divisor function sigma_k(n) for n an integer is defined as the sum of the kth powers of the (positive integer) divisors of n,

 sigma_k(n)=sum_(d|n)d^k.
(1)

It is implemented in the Wolfram Language as DivisorSigma[k, n].

The notations d(n) (Hardy and Wright 1979, p. 239), nu(n) (Ore 1988, p. 86), and tau(n) (Burton 1989, p. 128) are sometimes used for sigma_0(n), which gives the number of divisors of n. Rather surprisingly, the number of factors of the polynomial a^n-b^n are also given by d(n). The values of sigma_0(n) can be found as the inverse Möbius transform of 1, 1, 1, ... (Sloane and Plouffe 1995, p. 22). Heath-Brown (1984) proved that sigma_0(n)=sigma_0(n+1) infinitely often. The numbers having the incrementally largest number of divisors are called highly composite numbers. The function sigma_0(n) satisfies the identities

sigma_0(p^a)=a+1
(2)
sigma_0(p_1^(a_1)p_2^(a_2)...)=(a_1+1)(a_2+1)...,
(3)

where the p_i are distinct primes and p_1^(a_1)p_2^(a_2)... is the prime factorization of a number n.

The divisor function sigma_0(n) is odd iff n is a square number.

The function sigma_1(n) that gives the sum of the divisors of n is commonly written without the subscript, i.e., sigma(n).

As an illustrative example of computing sigma_k(n), consider the number 140, which has divisors d_i=1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, and 140, for a total of N=12 divisors in all. Therefore,

sigma_0(140)=N=12
(4)
sigma_1(140)=sum_(i=1)^(N)d_i=336
(5)
sigma_2(140)=sum_(i=1)^(N)d_i^2=27300
(6)
sigma_3(140)=sum_(i=1)^(N)d_i^3=3164112.
(7)

The following table summarized the first few values of sigma_k(n) for small k and n=1, 2, ....

kOEISsigma_k(n) for n=1, 2, ...
0A0000051, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, ...
1A0002031, 3, 4, 7, 6, 12, 8, 15, 13, 18, ...
2A0011571, 5, 10, 21, 26, 50, 50, 85, 91, 130, ...
3A0011581, 9, 28, 73, 126, 252, 344, 585, 757, 1134, ...

The sum of the divisors of n excluding n itself (i.e., the proper divisors of n) is called the restricted divisor function and is denoted s(n). The first few values are 0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, ... (OEIS A001065).

The sum of divisors sigma_1(N) can be found as follows. Let N=ab with a!=b and (a,b)=1. For any divisor d of N, d=a_ib_i, where a_i is a divisor of a and b_i is a divisor of b. The divisors of a are 1, a_1, a_2, ..., and a. The divisors of b are 1, b_1, b_2, ..., b. The sums of the divisors are then

sigma_1(a)=1+a_1+a_2+...+a
(8)
sigma_1(b)=1+b_1+b_2+...+b.
(9)

For a given a_i,

 a_i(1+b_1+b_2+...+b)=a_isigma_1(b).
(10)

Summing over all a_i,

 (1+a_1+a_2+...+a)sigma_1(b)=sigma_1(a)sigma_1(b),
(11)

so sigma_1(N)=sigma_1(ab)=sigma_1(a)sigma_1(b). Splitting a and b into prime factors,

 sigma_1(N)=sigma_1(p_1^(alpha_1))sigma_1(p_2^(alpha_2))...sigma_1(p_r^(alpha_r)).
(12)

For a prime power p_i^(alpha_i), the divisors are 1, p_i, p_i^2, ..., p_i^(alpha_i), so

 sigma_1(p_i^(alpha_i))=1+p_i+p_i^2+...+p_i^(alpha_i)=(p_i^(alpha_i+1)-1)/(p_i-1).
(13)

For N, therefore,

 sigma_1(N)=product_(i=1)^r(p_i^(alpha_i+1)-1)/(p_i-1)
(14)

(Berndt 1985).

For the special case of N a prime, (14) simplifies to

 sigma_1(p)=(p^2-1)/(p-1)=p+1.
(15)

Similarly, for N a power of two, (14) simplifies to

 sigma_1(2^alpha)=(2^(alpha+1)-1)/(2-1)=2^(alpha+1)-1.
(16)

The identities (◇) and (◇) can be generalized to

sigma_k(N)=sigma_k(p_1^(alpha_1))sigma_k(p_2^(alpha_2))...sigma_k(p_r^(alpha_r))
(17)
=product_(i=1)^(r)(p_i^((alpha_i+1)k)-1)/(p_i^k-1).
(18)

Sums involving the divisor function are given by

 sum_(n=1)^infty(sigma_0(n))/(n^s)=zeta^2(s)
(19)

for s>1,

 sum_(n=1)^infty(sigma_1(n))/(n^s)=zeta(s)zeta(s-1)
(20)

for s>2, and more generally,

 sum_(n=1)^infty(sigma_k(n))/(n^s)=zeta(s)zeta(s-k)
(21)

for s>1 and k>=0 (Hardy and Wright 1979, p. 250).

A generating function for sigma_0(n) is given by the Lambert series

L(x)=sum_(n=1)^(infty)(x^n)/(1-x^n)
(22)
=(psi_x(1)+ln(1-x))/(lnx)
(23)
=sigma_0(1)x+sigma_0(2)x^2+...
(24)
=x+2x^2+2x^3+3x^4+2x^5+...,
(25)

where phi_q(x) is a q-polygamma function.

The sigma_1(n) function has the series expansion

 sigma_1(n)=1/6npi^2[(1+((-1)^n)/(2^2))+(2cos(2/3npi))/(3^2)+(2cos(1/2npi))/(4^2)+(2[cos(2/5npi)+cos(4/5npi)])/(5^2)+...]
(26)

(Hardy 1999). Ramanujan gave the beautiful formula

 sum_(n=1)^infty(sigma_a(n)sigma_b(n))/(n^s)=(zeta(s)zeta(s-a)zeta(s-b)zeta(s-a-b))/(zeta(2s-a-b)),
(27)

where zeta(n) is the zeta function and R[s],R[s-a],R[s-b],R[s-a-b]>1 (Wilson 1923), which was used by Ingham in a proof of the prime number theorem (Hardy 1999, pp. 59-60). This gives the special case

 sum_(n=1)^infty([d(n)]^2)/(n^s)=([zeta(s)]^4)/(zeta(2s))
(28)

(Hardy 1999, p. 59).

Gronwall's theorem states that

 lim_(n->infty)^_(sigma_1(n))/(nlnlnn)=e^gamma,
(29)

where gamma is the Euler-Mascheroni constant (Hardy and Wright 1979, p. 266; Robin 1984). This can be written as an explicit inequality as

 (sigma_1(n))/(nlnlnn)<=e^gamma+c/((lnlnn)^2),
(30)

where gamma is the Euler-Mascheroni constant and where equality holds for n=12, giving

c=7/3(lnln12)-e^gamma(lnln12)^2
(31)
=0.648213649...
(32)

(Robin 1984, Theorem 2). In fact, the constant term can be dropped if the Riemann hypothesis holds, since the Riemann hypothesis is equivalent to the statement that

 (sigma_1(n))/(nlnlnn)<e^gamma
(33)

for all n>=5041 (Robin 1984, Theorem 1).

sigma_1(n) is a power of 2 iff n=1 or n is a product of distinct Mersenne primes (Sierpiński 1958/59, Sivaramakrishnan 1989, Kaplansky 1999). The first few such n are 1, 3, 7, 21, 31, 93, 127, 217, 381, 651, 889, 2667, ... (OEIS A046528), and the powers of 2 these correspond to are 0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10, 12, 12, 13, 14, ... (OEIS A048947).

Curious identities derived using modular form theory are given by

 sigma_3(n)-sigma_7(n)+120sum_(k=1)^(n-1)sigma_3(k)sigma_3(n-k)=0
(34)
 -10sigma_3(n)+21sigma_5(n)-11sigma_9(n)+5040sum_(k=1)^(n-1)sigma_3(k)sigma_5(n-k)=0
(35)

(Apostol 1997, p. 140), together with

 21sigma_5(n)-20sigma_7(n)-sigma_(13)(n)+10080sum_(k=1)^(n-1)sigma_5(n-k)sigma_7(k)=0
(36)
 -10sigma_3(n)+11sigma_9(n)-sigma_(13)(n)+2640sum_(k=1)^(n-1)sigma_3(n-k)sigma_9(k)=0
(37)
 -21sigma_5(n)+22sigma_9(n)-sigma_(13)(n)-2904sum_(k=1)^(n-1)sigma_9(n-k)sigma_9(k) 
 +504sum_(k=1)^(n-1)sigma_5(n-k)sigma_(13)(k)=0
(38)

(M. Trott, pers. comm.).

The divisor function sigma_1(n) (and, in fact, sigma_k(n) for k>=1) is odd iff n is a square number or twice a square number. The divisor function sigma_1(n) satisfies the congruence

 nsigma_1(n)=2 (mod phi(n)),
(39)

for all primes and no composite numbers with the exception of 4, 6, and 22 (Subbarao 1974).

The number of divisors d(n) is prime whenever sigma_1(n) itself is prime (Honsberger 1991). Factorizations of sigma_1(p^a) for prime p are given by Sorli.

DivisorFunctionSummatory

In 1838, Dirichlet showed that the average number of divisors of all numbers from 1 to n is asymptotic to

 (sum_(k=1)^(n)d(k))/n∼lnn+2gamma-1
(40)

(Conway and Guy 1996; Hardy 1999, p. 55; Havil 2003, pp. 112-113), as illustrated above, where the thin solid curve plots the actual values and the thick dashed curve plots the asymptotic function. This is related to the Dirichlet divisor problem, which seeks to find the "best" coefficient theta in

 sum_(k=1)^nd(k)=nlnn+(2gamma-1)n+O(n^theta)
(41)

(Hardy and Wright 1979, p. 264).

The summatory functions for sigma_a with a>1 are

 sum_(k=1)^nsigma_a(k)=(zeta(a+1))/(a+1)n^(a+1)+O(n^a).
(42)

For a=1,

 sum_(k=1)^nsigma_1(k)=(pi^2)/(12)n^2+O(nlnn)
(43)

(Hardy and Wright 1979, p. 266).

The divisor function can also be generalized to Gaussian integers. The definition requires some care since in principle, there is ambiguity as to which of the four associates is chosen for each divisor. Spira (1961) defines the sum of divisors of a complex number z by factoring z into a product of powers of distinct Gaussian primes,

 z=epsilonproductp_i^(k_i),
(44)

where epsilon is a unit and each p_i lies in the first quadrant of the complex plane, and then writing

 sigma_1(z)=product(p_i^(k_i+1)-1)/(p_i-1).
(45)

This makes sigma a multiplicative function and also gives |sigma_1(z)|>=z. This extension is implemented in the Wolfram Language as DivisorSigma[1, z, GaussianIntegers -> True]. The following table gives sigma_1(a+ib) for small nonnegative values of a and b.

a\b0123456
112+i2+2i5+5i2+4i6+8i2+6i
22+3i3+i5i3+3i-2+10i3+5i-5+15i
342+6i4+2i8+4i6+5i9+7i8+8i
4-4+5i5+i3+11i-1+6i-8+i5+5i-3+15i
54+8i3+9i6+2i10i6+4i20i6+6i
68+12i7+i-10+10i12+4i2+16i7+5i20i

See also

Dirichlet Divisor Problem, Distinct Prime Factors, Divisor, Divisor Product, Even Divisor Function, Factor, Fermat's Divisor Problem, Greatest Prime Factor, Gronwall's Theorem, Highly Composite Number, Least Prime Factor, Multiperfect Number, Odd Divisor Function, Ore's Conjecture, Perfect Number, Prime Factor, Refactorable Number, Restricted Divisor Function, Robin's Theorem, Silverman Constant, Sociable Numbers, Sum of Squares Function, Superabundant Number, Tau Function, Totient Function, Totient Valence Function, Twin Peaks, Unitary Divisor Function Explore this topic in the MathWorld classroom

Related Wolfram sites

http://functions.wolfram.com/NumberTheoryFunctions/DivisorSigma/

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). "Divisor Functions." §24.3.3 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 827, 1972.Apostol, T. M. Modular Functions and Dirichlet Series in Number Theory, 2nd ed. New York: Springer-Verlag, p. 140, 1997.Berndt, B. C. Ramanujan's Notebooks: Part I. New York: Springer-Verlag, p. 94, 1985.Burton, D. M. Elementary Number Theory, 4th ed. Boston, MA: Allyn and Bacon, 1989.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 260-261, 1996.Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 279-325, 2005.Dirichlet, G. L. "Sur l'usage des séries infinies dans la théorie des nombres." J. reine angew. Math. 18, 259-274, 1838.Guy, R. K. "Solutions of msigma(m)=nsigma(n)," "Analogs with d(n), sigma_k(n)," "Solutions of sigma(n)=sigma(n+1)," and "Solutions of sigma(q)+sigma(r)=sigma(q+r)." §B11, B12, B13 and B15 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 67-70, 1994.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, pp. 55 and 141, 1999.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Oxford University Press, pp. 354-355, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.Heath-Brown, D. R. "A Parity Problem from Sieve Theory." Mathematika 29, 1-6, 1982.Heath-Brown, D. R. "The Divisor Function at Consecutive Integers." Mathematika 31, 141-149, 1984.Honsberger, R. More Mathematical Morsels. Washington, DC: Math. Assoc. Amer., pp. 250-251, 1991.Kaplansky, I. "The First Two Chapters of Dickson's History." Unpublished manuscript, Apr. 1999.Nagell, T. Introduction to Number Theory. New York: Wiley, pp. 26-27, 1951.Ore, Ø. Number Theory and Its History. New York: Dover, 1988.Robin, G. "Grandes valeurs de la fonction somme des diviseurs et hypothese de Riemann." J. Math. Pures Appl. 63, 187-213, 1984.Sierpiński, W. "Sur les nombres dont la somme de diviseurs est une puissance du nombre 2." Calcutta Math. Soc. Golden Jubilee Commemoration 1958/59, Part I. Calcutta: Calcutta Math. Soc., pp. 7-9, 1963.Sloane, N. J. A. Sequences A000005, A000203, A001065, A001157, A001158, A046528, and A048947 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Sivaramakrishnan, R. Classical Theory of Arithmetic Functions. New York: Dekker, 1989.Sorli, R. "Factorization Tables." http://www-staff.maths.uts.edu.au/~rons/fact/fact.htm.Spira, R. "The Complex Sum of Divisors." Amer. Math. Monthly 68, 120-124, 1961.Subbarao, M. V. "On Two Congruences for Primality." Pacific J. Math. 52, 261-268, 1974.Wilson, B. M. "Proofs of Some Formulae Enunciated by Ramanujan." Proc. London Math. Soc. 21, 235-255, 1923.

Referenced on Wolfram|Alpha

Divisor Function

Cite this as:

Weisstein, Eric W. "Divisor Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DivisorFunction.html

Subject classifications