282 HISTORY OF THE THEORY OF NUMBERS. [CHAP.X
Let S'(ri) be the sum of the odd divisors of n, and Cn be the number of all combinations without repetitions with the sum n, so that C7 = 5. Then
D(ri) = -D(n-l) -D(n-3)-D(n-6)- ..., D(n) = /S'(n) -S(n). A complicated recursion formula for r(n)is derived from
log{(l-aO(l-«')*(!-a8)*. ..}==-£ -r(n)of.
n* in-Complicated recursion formulas are found for the number of integers <m not factors of m, and for the sum of these integers. A recursion formula for the sum sr(ri) of the divisors ^r of n is obtained by expanding
log {l-z)(l-z2).. .(1-af)} = - S isr(n)a;n.
n«l?l
Jacobi16 proved (1).
Dirichlet17 obtained approximations to T(n). An integer s^n occurs in as many terms of this sum as there are multiples of s among 1, 2,..., n. The number of these multiples is [n/s], the greatest integer ^n/s. Hence
This sum is approximately the product of n by
Hence T(ri) is of the same order of magnitude as n log n.
Let Ai be the least integer gz^/n and set ?==[n//i]. Then if 0(2) is any function and G(x) =0(1) +0(2) + . . .
s of r5
«.i LLs
In particular, if 0(s) = 1,
Giving to [n/s] the approximation n/s, we see that (7) T(rc)=n log
where c is of the same order of magnitude as Vn.
Let p(n) be the number of distinct prime factors >1 of n. Then 2p(n) is the number of ways of factoring n into two relatively prime factors, taking
"Jour, fur Math., 32, 1846, 164; 37, 1848, 67, 73.
"Abhand. Ak. Wiss. Berlin, 1849, Math., 69-83; Werke, 2, 49-66. French transl., Jour, de Math., (2), 1, 1856, 353-370.