Parity of the Sums of the Number of Divisors

Number Theory Level 4

Define $\tau(n)$ to be the number of positive divisors of $n$ . Let $S_n=\tau(1)+\tau(2)+ \dots+\tau(n)$ . For how many $n \leq 2008$ is $S_n$ odd?

The answer is 990.

1 solution

Bogdan Simeonov
May 2, 2014

If n is not a perfect square, $\tau(n)\equiv0\pmod2$ If n is a perfect square, $\tau(n)\equiv1\pmod2$

So the sum above is congruent to $\lfloor{\sqrt{n}}\rfloor\pmod2$ .

Let $n=x^2+k,0\leq k<2x+1$

Then $\lfloor{\sqrt{n}}\rfloor=x$ .

So $x=1,3,5...43$ , because $45^2-1>2008$ .

The sum of all n's in that form is

$(2.1+1)+(2.3+1)+(2.5+1)+...+(2.43+1)=2.22^2+22=\boxed{990}$ .

We used the fact that the sum of the odd integers up to 2k-1 is $k^2$ .

By the way Finn, your title is wrong!It says "Parity of the sum of the sum of divisors",but it has to be "Parity if the sums of the number of divisors", because $\tau(n)$ is the number of the divisors of n :D

Bogdan Simeonov - 7 years, 1 month ago

Eh, I guess. But great solution! :D

Finn Hulse - 7 years, 1 month ago

@Silas Hundt can you fix this? Thanks. :D

Finn Hulse - 7 years ago

@Finn Hulse , you have to be careful with your phrasing.

Let $\tau (n)$ be the number of positive divisors of a positive integer $n$ . Those words are very important. If you miss the first ' positive ', then the problem becomes trivial.

EDIT: The problem's been edited now.

Mursalin Habib - 7 years ago

Parity of the Sums of the Number of Divisors

The answer is 990.

1 solution

0 pending reports