# How to find how many number has even value of sigma function?

I have to find how many integers from $1$ to $n$ $(n\leq10^{12})$ have even value of $\sigma$.

$\sigma(n)$ = sum of all divisors of $n$ .

-

It is easier to compute the number $N$ of integers $n$ is our range such that $\sigma(n)$ is odd, and then subtract $N$ from $10^{12}$.

Note that $\sigma(n)$ is odd if $n$ is a power of $2$. Also, $\sigma(n)$ is odd if $n$ is $p^k$, where $p$ is an odd prime and $k$ is even. If $n=p^k$ for an odd prime $p$, and $k$ is odd, then $\sigma(n)$ is even.

The $\sigma$ function is multiplicative, meaning that if $a$ and $b$ are relatively prime then $\sigma(ab)=\sigma(a)\sigma(b)$. Thus any odd prime occurring to an odd power in the prime power factorization of $n$ will make $\sigma(n)$ even.

So $\sigma(n)$ is odd if and only if $n$ is a power of $2$ times a perfect square. For counting, it is easier to express this by saying that $\sigma(n)$ is odd iff $n$ is a perfect square or twice a perfect square.

Now everything is easy. There are $10^6$ perfect squares in our range. And to count the numbers that are twice a perfect square, there are just as many as there are squares up to $5\times 10^{11}$. To find this number, take the integer part of the square root of $5\times 10^{11}$.

A general formula: Let $B$ be a positive integer. Then the number of positive integers $n\le B$ such that $\sigma(n)$ is odd is $\lfloor\sqrt{B}\rfloor +\lfloor\sqrt{B/2}\rfloor$, where $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$. Thus the number of positive integers $n\le B$ such that $\sigma(n)$ is even is $$B-\lfloor\sqrt{B}\rfloor- \lfloor\sqrt{B/2}\rfloor.$$

-
thanks a lot . exactly what i wanted . – palatok Feb 12 '13 at 13:04