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