# §27.11 Asymptotic Formulas: Partial Sums

The behavior of a number-theoretic function $f(n)$ for large $n$ is often difficult to determine because the function values can fluctuate considerably as $n$ increases. It is more fruitful to study partial sums and seek asymptotic formulas of the form

 27.11.1 $\sum_{n\leq x}f(n)=F(x)+O\left(g(x)\right),$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $n$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.11.E1 Encodings: TeX, pMML, png See also: Annotations for §27.11 and Ch.27

where $F(x)$ is a known function of $x$, and $O\left(g(x)\right)$ represents the error, a function of smaller order than $F(x)$ for all $x$ in some prescribed range. For example, Dirichlet (1849) proves that for all $x\geq 1$,

 27.11.2 $\sum_{n\leq x}d\left(n\right)=x\ln x+(2\gamma-1)x+O\left(\sqrt{x}\right),$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\gamma$: Euler’s constant, $d_{\NVar{k}}\left(\NVar{n}\right)$: divisor function, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.3 III Referenced by: §27.11, §27.11, Erratum (V1.1.8) for Section 27.11 Permalink: http://dlmf.nist.gov/27.11.E2 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

where $\gamma$ is Euler’s constant (§5.2(ii)). Dirichlet’s divisor problem (unsolved as of 2022) is to determine the least number $\theta_{0}$ such that the error term in (27.11.2) is $O\left(x^{\theta}\right)$ for all $\theta>\theta_{0}$. Huxley (2003) proves that $\theta_{0}\leq\frac{131}{416}$.

Equations (27.11.3)–(27.11.11) list further asymptotic formulas related to some of the functions listed in §27.2. They are valid for all $x\geq 2$. The error terms given here are not necessarily the best known.

 27.11.3 $\sum_{n\leq x}\frac{d\left(n\right)}{n}=\frac{1}{2}(\ln x)^{2}+2\gamma\ln x+O% \left(1\right),$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\gamma$: Euler’s constant, $d_{\NVar{k}}\left(\NVar{n}\right)$: divisor function, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E3 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

where $\gamma$ again is Euler’s constant.

 27.11.4 $\displaystyle\sum_{n\leq x}\sigma_{1}\left(n\right)$ $\displaystyle=\frac{{\pi}^{2}}{12}x^{2}+O\left(x\ln x\right).$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\pi$: the ratio of the circumference of a circle to its diameter, $\sigma_{\NVar{\alpha}}\left(\NVar{n}\right)$: sum of powers of divisors of a number, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.3 III (in slightly different form) Permalink: http://dlmf.nist.gov/27.11.E4 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27 27.11.5 $\displaystyle\sum_{n\leq x}\sigma_{\alpha}\left(n\right)$ $\displaystyle=\frac{\zeta\left(\alpha+1\right)}{\alpha+1}x^{\alpha+1}+O\left(x% ^{\beta}\right),$ $\alpha>0$, $\alpha\neq 1$, $\beta=\max(1,\alpha)$.
 27.11.6 $\displaystyle\sum_{n\leq x}\phi\left(n\right)$ $\displaystyle=\frac{3}{{\pi}^{2}}x^{2}+O\left(x\ln x\right).$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\phi\left(\NVar{n}\right)$: Euler’s totient, $\pi$: the ratio of the circumference of a circle to its diameter, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.2 III (in slightly different form) Permalink: http://dlmf.nist.gov/27.11.E6 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27 27.11.7 $\displaystyle\sum_{n\leq x}\frac{\phi\left(n\right)}{n}$ $\displaystyle=\frac{6}{{\pi}^{2}}x+O\left(\ln x\right).$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\phi\left(\NVar{n}\right)$: Euler’s totient, $\pi$: the ratio of the circumference of a circle to its diameter, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.11.E7 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27
 27.11.8 $\sum_{p\leq x}\frac{1}{p}=\ln\ln x+A+O\left(\frac{1}{\ln x}\right),$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\ln\NVar{z}$: principal branch of logarithm function, $p,p_{1},\ldots$: prime numbers, $x$: real number and $A$: constant Permalink: http://dlmf.nist.gov/27.11.E8 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

where $A$ is a constant.

 27.11.9 $\sum_{\begin{subarray}{c}p\leq x\\ p\equiv h\!\!\!\!\!\pmod{k}\end{subarray}}\frac{1}{p}=\frac{1}{\phi\left(k% \right)}\ln\ln x+B+O\left(\frac{1}{\ln x}\right),$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\phi\left(\NVar{n}\right)$: Euler’s totient, $\equiv$: modular equivalence, $\ln\NVar{z}$: principal branch of logarithm function, $k$: positive integer, $p,p_{1},\ldots$: prime numbers and $x$: real number Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E9 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

where $\left(h,k\right)=1$, $k>0$, and $B$ is a constant depending on $h$ and $k$.

 27.11.10 $\sum_{p\leq x}\frac{\ln p}{p}=\ln x+O\left(1\right).$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\ln\NVar{z}$: principal branch of logarithm function, $p,p_{1},\ldots$: prime numbers and $x$: real number Permalink: http://dlmf.nist.gov/27.11.E10 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27
 27.11.11 $\sum_{\begin{subarray}{c}p\leq x\\ p\equiv h\!\!\!\!\!\pmod{k}\end{subarray}}\frac{\ln p}{p}=\frac{1}{\phi\left(k% \right)}\ln x+O\left(1\right),$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\phi\left(\NVar{n}\right)$: Euler’s totient, $\equiv$: modular equivalence, $\ln\NVar{z}$: principal branch of logarithm function, $k$: positive integer, $p,p_{1},\ldots$: prime numbers and $x$: real number Referenced by: §27.11, §27.11 Permalink: http://dlmf.nist.gov/27.11.E11 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

where $\left(h,k\right)=1$, $k>0$.

Letting $x\to\infty$ in (27.11.9) or in (27.11.11) we see that there are infinitely many primes $p\equiv h\pmod{k}$ if $h,k$ are coprime; this is Dirichlet’s theorem on primes in arithmetic progressions.

 27.11.12 $\sum_{n\leq x}\mu\left(n\right)=O\left(xe^{-C\sqrt{\ln x}}\right),$ $x\to\infty$, ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\mu\left(\NVar{n}\right)$: Möbius function, $\mathrm{e}$: base of natural logarithm, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer, $x$: real number and $C$: constant A&S Ref: 24.3.1 III Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E12 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

for some positive constant $C$,

 27.11.13 $\lim_{x\to\infty}\frac{1}{x}\sum_{n\leq x}\mu\left(n\right)=0,$ ⓘ Symbols: $\mu\left(\NVar{n}\right)$: Möbius function, $n$: positive integer and $x$: real number Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E13 Encodings: TeX, pMML, png See also: Annotations for §27.11 and Ch.27
 27.11.14 $\lim_{x\to\infty}\sum_{n\leq x}\frac{\mu\left(n\right)}{n}=0,$ ⓘ Symbols: $\mu\left(\NVar{n}\right)$: Möbius function, $n$: positive integer and $x$: real number A&S Ref: 24.3.1 III Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E14 Encodings: TeX, pMML, png See also: Annotations for §27.11 and Ch.27
 27.11.15 $\lim_{x\to\infty}\sum_{n\leq x}\frac{\mu\left(n\right)\ln n}{n}=-1.$ ⓘ Symbols: $\mu\left(\NVar{n}\right)$: Möbius function, $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.1 III Referenced by: §27.11, §27.11 Permalink: http://dlmf.nist.gov/27.11.E15 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.11 and Ch.27

Each of (27.11.13)–(27.11.15) is equivalent to the prime number theorem (27.2.3). The prime number theorem for arithmetic progressions—an extension of (27.2.3) and first proved in de la Vallée Poussin (1896a, b)—states that if $\left(h,k\right)=1$, then the number of primes $p\leq x$ with $p\equiv h\pmod{k}$ is asymptotic to $x/(\phi\left(k\right)\ln x)$ as $x\to\infty$.