Problem:
For positive integers n, let Ï„(n) denote the number of positive integer divisors of n, including 1 and n. For example, Ï„(1)=1 and Ï„(6)=4. Define S(n) by
S(n)=τ(1)+τ(2)+⋯+τ(n)
Let a denote the number of positive integers n≤2005 with S(n) odd, and let b denote the number of positive integers n≤2005 with S(n) even. Find ∣a−b∣.
Solution:
If d is a divisor of n, then so is dn​. Thus the number of divisors of n must be even unless, for some d,d=dn​, that is, n=d2. Hence τ(n) is odd if and only if n is a square. Therefore, as n increases, S(n) changes parity only when n is a square. Thus S(n) is odd for 12≤n≤22−1, even for 22≤n≤32−1, odd for 32≤n≤42−1, and so on. Consequently
a​=(22−1−12+1)+(42−1−32+1)+(62−1−52+1)+⋯+(442−1−432+1)=(22−12)+(42−32)+(62−52)+⋯+(442−432)=(2+1)(2−1)+(4+3)(4−3)+(6+5)(6−5)+⋯+(44+43)(44−43)=1+2+3+⋯+44=44⋅45/2=990​
Then b=2005−990=1015, so ∣a−b∣=25​.
The problems on this page are the property of the MAA's American Mathematics Competitions