Benchmarks

234 7. Divisor Functions

This completes the proof. ■

Theorem 7.4 For $x\; \backslash ge\; 1$ ,

$$\backslash Delta(x)\; =\; \backslash sum\_\{n\; \backslash le\; x\}\; (\backslash log\; n\; -\; d(n)\; +\; 2\backslash gamma)\; =\; O\backslash left(x^\{1/2\}\backslash right).$$

Proof. By Theorem 7.3 we have

$$\backslash sum\_\{n\; \backslash le\; x\}\; d(n)\; =\; x\; \backslash log\; x\; +\; (2\backslash gamma\; -\; 1)x\; +\; O\backslash left(x^\{1/2\}\backslash right).$$

By Theorem 6.4 we have

$$\backslash sum\_\{n\; \backslash le\; x\}\; \backslash log\; n\; =\; x\; \backslash log\; x\; -\; x\; +\; O(\backslash log\; x).$$

Subtracting the first equation from the second, we obtain

$$\backslash sum\_\{n\; \backslash le\; x\}\; (\backslash log\; n\; -\; d(n)\; +\; 2\backslash gamma)\; =\; O\backslash left(x^\{1/2\}\backslash right)\; -\; 2\backslash gamma\backslash \{x\backslash \}\; +\; O(\backslash log\; x)\; =\; O\backslash left(x^\{1/2\}\backslash right).$$

An ordered factorization of the positive integer $n$ into exactly $\backslash ell$ factors is an $\backslash ell$ -tuple $(d\_1,\; \backslash dots,\; d\_\backslash ell)$ such that $n\; =\; d\_1\; \backslash cdots\; d\_\backslash ell$ . The divisor function $d(n)$ counts the number of ordered factorizations of $n$ into exactly two factors, since each factorization $n\; =\; dd\text{'}$ is completely determined by the first factor $d$ . For every positive integer $\backslash ell$ , we define the arithmetic function $d\_\backslash ell(n)$ as the number of factorizations of $n$ into exactly $\backslash ell$ factors. Then $d\_1(n)\; =\; 1$ and $d\_2(n)\; =\; d(n)$ for all $n$ .