how to find odd number of odd divisors between 1 to n

Question

Like
In range of 1 to 3 there are 2 numbers who has odd number of odd divisors
In range 5 to 10 there are 2 numbers who has odd number of odd divisors
In range 10 to 15 there is no numbers who has odd number of odd divisors

Answer 1

A positive integer has an odd number of total factors if and only if it is a perfect square. The reason for this is that normally factors can be divided into pairs, $(r,n/r)$, but if $n$ is a perfect square there is also $\sqrt n$ which only gets paired with itself.

So an odd integer has an odd number of odd factors if and only if it is a perfect square (since all its factors are odd). If you want the odd factors of an even number $n$, first write it as a product of a power of $2$ and an odd number (there is always a unique way to do this). Then the odd factors of $n$ are precisely the factors of the odd number.

Consequently a number has an odd number of odd factors if and only if it is a power of $2$ times the square of an odd number. For example $72=2^3\times 3^2$, or $361=2^0\times19^2$.

Answer 2

I agree with @EspeciallyLime's answer, but I think this is a more intuitive way to think about it.

The formula for the number of odd divisors of a number with prime factorization $$n=2^{a_2}3^{a_3}5^{a_5}...$$ where $a_{\textrm{prime}}\in\mathbb Z,\;a_{\textrm{prime}}>0$ is$$(a_3+1)(a_5+1)(a_7+1)...$$ Notice that $a_2$ doesn't change the number of odd divisors, but in order for the number to have an odd number of divisors, all of the multiplicands must be odd, so the corresponding $a$ values must be even. This is equivalent to saying that all number that have an odd number of odd divisors are of the form $$2^k\cdot n^2$$where $k\geq0,\; n\geq1$.