Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$ .

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.$$

share|improve this answer
    
thanks a lot . exactly what i wanted . –  palatok Feb 12 '13 at 13:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.