Question

For positive integers $n,$ let $\tau(n)$ denote the number of positive integer divisors of $n,$ including $1$ and $n.$ For example, $\tau(1) = 1$ and $\tau(6) = 4.$ Define $S(n)$ by $S(n) = \tau(1) + \tau(2) + \cdots + \tau(n).$ Let $a$ denote the number of positive integers $n \le 2005$ with $S(n)$ odd, and let $b$ denote the number of positive integers $n \le 2005$ with $S(n)$ even. Find $|a - b|.$

Answer

Solution:

Divisors of $n$ pair up as $d$ and $\frac{n}{d},$ so $\tau(n)$ is odd exactly when $n$ is a perfect square. Hence $S(n)$ changes parity exactly at the squares, which means $S(n)$ is odd exactly when the number of squares up to $n,$ namely $\lfloor\sqrt{n}\rfloor,$ is odd.

For each $k,$ there are $2k + 1$ integers $n$ with $\lfloor\sqrt{n}\rfloor = k,$ namely $k^2 \le n \le k^2 + 2k.$ Since $44^2 = 1936 \le 2005 \lt 2025 = 45^2,$ the odd values $k = 1, 3, \ldots, 43$ all have their full blocks within range, so $a = \sum_{k \text{ odd},\, k \le 43} (2k + 1) = 2(1 + 3 + \cdots + 43) + 22 = 2 \cdot 484 + 22 = 990.$

Then $b = 2005 - 990 = 1015,$ and $|a - b| = 25.$

2005 AIME I Problem 12

Solution:

Problem 12 in Other Years