4
$\begingroup$

Define $\sigma(i)$ to be the sum of all the divisors of $i$. For example, $σ(24) = 1+2+3+4+6+8+12+24 = 60$.

Given an integer $n$, how can we count the number of integers $i$, less than or equal to $n$, such that $\sigma(i)$ is even?

$\endgroup$
4
  • $\begingroup$ Is this an algorithm problem? Assuming it is, retagging as elementary-number-theory. $\endgroup$
    – Aryabhata
    Mar 28, 2015 at 19:36
  • $\begingroup$ yes , this is an algorithm problem. I need a solution of order sqrt(n) $\endgroup$ Mar 28, 2015 at 19:40
  • $\begingroup$ This is usually called $\sigma$ (the Greek letter sigma) rather than SOD. $\endgroup$
    – user155234
    Mar 28, 2015 at 19:47
  • $\begingroup$ yes , I edited my question. @ Albert $\endgroup$ Mar 28, 2015 at 20:25

1 Answer 1

5
$\begingroup$

Write $n=2^m(2q+1)$, and let $\sigma(n)$ denote the sum of divisors of $n$, we have: $$\sigma(n)=\sum_{d|n}d=\underbrace{\sum_{d|n, d \text{ even}} d}_{\text{even}}+\underbrace{\sum_{d|n, d \text{ odd}} d}_{=\sigma(2q+1)} $$ So $\sigma(n)$ is odd if and only if $\sigma(2q+1)$ is odd, let $d_1,\cdots,d_r$ be all divisors of $2q+1$ then: $$\sigma(2q+1)=d_1+d_2+\cdots+d_r $$ we know that all $d_i$ are odd so $\sigma(2q+1)$ is odd if and only if $r$ is odd, or in other words the number of divisors of $2q+1$ is odd, but the number of divisors of an integer $a$ is odd if and only if $a$ is a square, finally $\sigma(n)$ is odd if and only if $2q+1$ is odd

so the sum of divisor of $n$ is odd if and only if it can be written as $2q^2$ or $q^2$

  • The number of integers of the form $q^2$ less then $N$ is $\lfloor \sqrt n \rfloor $
  • The number of integers of the form $2q^2$ less than $N$ is $\left \lfloor \sqrt \frac{n}{2} \right \rfloor $

finally: the number of integers $n\leq N$ such that σ(i) is even is: $$N-\lfloor \sqrt N \rfloor - \left \lfloor \sqrt \frac{N}{2} \right \rfloor $$

$\endgroup$
2
  • $\begingroup$ your formula worked but how explain briefly please. @Elaqqad $\endgroup$ Mar 28, 2015 at 19:54
  • $\begingroup$ now its clear. @Elaqqad $\endgroup$ Mar 29, 2015 at 12:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .