info prev up next book cdrom email home

Divisor Function

\begin{figure}\begin{center}\BoxedEPSF{DivisorFunction.epsf scaled 1050}\end{center}\end{figure}

$\sigma_k(n)$ is defined as the sum of the $k$th Powers of the Divisors of $n$. The function $\sigma_0(n)$ gives the total number of Divisors of $n$ and is often denoted $d(n)$, $\nu(n)$, $\tau(n)$, or $\Omega(n)$ (Hardy and Wright 1979, pp. 354-355). The first few values of $\sigma_0(n)$ are 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, ... (Sloane's A000005). The function $\sigma_1(n)$ is equal to the sum of Divisors of $n$ and is often denoted $\sigma(n)$. The first few values of $\sigma(n)$ are 1, 3, 4, 7, 6, 12, 8, 15, 13, 18, ... (Sloane's A000203). The first few values of $\sigma_2(n)$ are 1, 5, 10, 21, 26, 50, 50, 85, 91, 130, ... (Sloane's A001157). The first few values of $\sigma_3(n)$ are 1, 9, 28, 73, 126, 252, 344, 585, 757, 1134, ... (Sloane's A001158).


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, ... (Sloane's A001065).


As an illustrative example, 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$ of them). Therefore,

$\displaystyle d(140)$ $\textstyle =$ $\displaystyle N=12$ (1)
$\displaystyle \sigma(140)$ $\textstyle =$ $\displaystyle \sum_{i=1}^N d_i=336$ (2)
$\displaystyle \sigma_2(140)$ $\textstyle =$ $\displaystyle \sum_{i=1}^N {d_i}^2=27,300$ (3)
$\displaystyle \sigma_3(140)$ $\textstyle =$ $\displaystyle \sum_{i=1}^N {d_i}^3=3,164,112.$ (4)


The $\sigma(n)$ function has the series expansion
$\sigma(n) = {\textstyle{1\over 6}} \pi^2n\left[{1+{(-1)^n\over 2^2}+{2\cos({\textstyle{2\over 3}} n\pi)\over 3^2}}\right.$
$ \left.{+ {2\cos({\textstyle{1\over 2}}n\pi)\over 4^2}+{2[\cos({\textstyle{2\over 5}} n\pi)+\cos({\textstyle{4\over 5}} n\pi)]\over 5^2}+\ldots}\right]\quad$ (5)
(Hardy 1959). It also satisfies the Inequality


\begin{displaymath}
{\sigma(n)\over n\ln\ln n}\leq e^\gamma+{2(1-\sqrt{2}\,)+\ga...
...}+{\mathcal O}\left({1\over\sqrt{\ln n}\,(\ln\ln n)^2}\right),
\end{displaymath} (6)

where $\gamma$ is the Euler-Mascheroni Constant (Robin 1984, Erdös 1989).


Let a number $n$ have Prime factorization

\begin{displaymath}
n=\prod_{j=1}^r {p_j}^{\alpha_j},
\end{displaymath} (7)

then
\begin{displaymath}
\sigma(n)=\prod_{j=1}^r {{p_j}^{\alpha_j+1}-1\over p_j-1}
\end{displaymath} (8)

(Berndt 1985). Gronwall's Theorem states that
\begin{displaymath}
\overline{\lim_{n\to\infty}} {\sigma(n)\over n\ln \ln n}=e^\gamma,
\end{displaymath} (9)

where $\gamma$ is the Euler-Mascheroni Constant.


\begin{figure}\begin{center}\BoxedEPSF{DivisorFunctionSummatory.epsf}\end{center}\end{figure}

In general,

\begin{displaymath}
\sigma_k(n)\equiv \sum_{d\vert n} d^k.
\end{displaymath} (10)

In 1838, Dirichlet showed that the average number of Divisors of all numbers from 1 to $n$ is asymptotic to
\begin{displaymath}
{\sum_{i=1}^n \sigma_0(i)\over n}\sim\ln n+2\gamma-1
\end{displaymath} (11)

(Conway and Guy 1996), as illustrated above, where the thin solid curve plots the actual values and the thick dashed curve plots the asymptotic function.


A curious identity derived using Modular Form theory is given by

\begin{displaymath}
\sigma_7(n)=\sigma_3(n)+120\sum_{k=1}^{n-1}\sigma_3(k)\sigma_3(n-k).
\end{displaymath} (12)


The asymptotic Summatory Function of $\sigma_0(n)=\Omega(n)$ is given by

\begin{displaymath}
\sum_{k=2}^n \Omega(k)=n\ln\ln n+B_2+o(n),
\end{displaymath} (13)

where
\begin{displaymath}
B_2=\gamma+\sum_{p{\rm\ prime}} \left[{\ln(1-p^{-1})+{1\over p-1}}\right]\approx 1.034653
\end{displaymath} (14)

(Hardy and Wright 1979, p. 355). This is related to the Dirichlet Divisor Problem. The Summatory Functions for $\sigma_a$ with $a>1$ are
\begin{displaymath}
\sum_{k=1}^n \sigma_a(k) = {\zeta(a+1)\over a+1}n^{a+1} +{\mathcal O}(n^a).
\end{displaymath} (15)

For $a=1$,
\begin{displaymath}
\sum_{k=1}^n \sigma_1(k) ={\pi^2\over 12}n^2+{\mathcal O}(n\ln n).
\end{displaymath} (16)

The divisor function is Odd Iff $n$ is a Square Number or twice a Square Number. The divisor function satisfies the Congruence
\begin{displaymath}
n\sigma(n)\equiv 2\ \left({{\rm mod\ } {\phi(n)}}\right),
\end{displaymath} (17)

for all Primes and no Composite Numbers with the exception of 4, 6, and 22 (Subbarao 1974). $\tau(n)$ is Prime whenever $\sigma(n)$ is (Honsberger 1991). Factorizations of $\sigma(p^a)$ for Prime $p$ are given by Sorli.

See also Dirichlet Divisor Problem, Divisor, Factor, Greatest Prime Factor, Gronwall's Theorem, Least Prime Factor, Multiply Perfect Number, Ore's Conjecture, Perfect Number, r(n), Restricted Divisor Function, Silverman Constant, Tau Function, Totient Function, Totient Valence Function, Twin Peaks


References

Abramowitz, M. and Stegun, C. 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.

Berndt, B. C. Ramanujan's Notebooks: Part I. New York: Springer-Verlag, p. 94, 1985.

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: Chelsea, pp. 279-325, 1952.

Dirichlet, G. L. ``Sur l'usage des séries infinies dans la théorie des nombres.'' J. reine angew. Math. 18, 259-274, 1838.

Erdös, P. ``Ramanujan and I.'' In Proceedings of the International Ramanujan Centenary Conference held at Anna University, Madras, Dec. 21, 1987. (Ed. K. Alladi). New York: Springer-Verlag, pp. 1-20, 1989.

Guy, R. K. ``Solutions of $m\sigma(m)=n\sigma(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, p. 141, 1959.

Hardy, G. H. and Weight, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Oxford University Press, pp. 354-355, 1979.

Honsberger, R. More Mathematical Morsels. Washington, DC: Math. Assoc. Amer., pp. 250-251, 1991.

Robin, G. ``Grandes valeurs de la fonction somme des diviseurs et hypothese de Riemann.'' J. Math. Pures Appl. 63, 187-213, 1984.

Sloane, N. J. A. Sequences A000005/M0246, A000203/M2329 A001065/M2226, A001157/M3799, and A001158/M4605, in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Subbarao, M. V. ``On Two Congruences for Primality.'' Pacific J. Math. 52, 261-268, 1974.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-24