How to know how many times the number of divisors for the numbers from 1-5000 are odd?

Question

I have a question I can not answer myself. For every number from 1-5000 I write down the number of divisors. Example: 1 has 1 divisor, 2 has 2 and 10 has 4 (1, 2, 5, 10). I do this up to the number 5000. Know I want to know how many times the number of divisors is odd and how many times it is even.

I am looking forward to your thougts! Finn

Answer 1

Hint: $4$ has an odd number of divisors. (Why?)

Hint: $576$ has an odd number of divisors. (Why?)

But numbers like $12$ have an even number of divisors.

Each integer can be expressed as $n=ab$ (even if $a=1$ and $b=n$). So for every divisor $a$, there's a matching divisor $b$ such that $ab=n$.

What happens with numbers like $4$ and $576$ is that $a=b$ for one of the pairs, and you get an odd number of divisors overall.

Answer 2

It is well known that if $$n=\prod p_i^{\alpha_i}$$ then the number of divisors of $n$ is equal to $$\prod (\alpha_i+1)$$ Hence in order to have an odd number of divisors you need all the exponents $\alpha_i$ be even because if not then the numbers of factors will be even.

Since $$70^2\lt 5000\lt 71^2$$ you have $70$ times for which the number of divisors is odd an $5000-70=4930$ times for wich the number of divisors is even.