TITLE: How to find how many number has even value of sigma function?
QUESTION [3 upvotes]: 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$ .

REPLY [7 votes]: 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.$$
{"set_name": "stack_exchange", "score": 3, "question_id": 301151}