# parity of sum of divisors of number n

What is the fastest way to calculate parity of sum of divisors of a number without computing the sum of divisors of the given number $n$ by the formula stated in these answers formula to calculate sum of divisors on mathematics stackexchange

I also came across this code which calculates the parity of sum of divisors of a number n but couldn't get the logic .

// divsum stores the parity of sum of divisors of number n

int calc(long long n) {
bool divisibleBy2 = n % 2 == 0;
while (n % 2 == 0) n /= 2;
// n odd
int nFactors = int (divisibleBy2);
int divSumParity = 1;
for (int i = 2; (long long) i * i * i <= n; i ++) {
if (n % i == 0) {
int e = 0;
while (n % i == 0) n /= i, e ++;
if (e % 2 == 1) divSumParity = 0;
nFactors ++;
}
}
if (n > 1) {
if (isSquare(n)) {
nFactors += 1;
} else if (isPrime(n)) {
nFactors += 1;
divSumParity = 0;
} else {
nFactors += 2;
divSumParity = 0;
}
}
return 2*(nFactors%2) + divSumParity;
}


To calculate the parity, we need only consider all odd divisors of $n$. That is, if $n=2^km$ with $m$ odd, then we need only check the parity of the sum of divisors of $m$, which just means we need to find out of the number of divisors of $m$ is odd or even. And for this, note that divisors come in pairs except for a perfect square. Thus this code would do the job better and faster:

int DivisorSumParity(unsigned long long n) {
assert(n != 0);
while (n % 2 == 0) n /=2;
return issquare(n);
}

• @the value of n can be as large as 10^15 – satyajeet jha Apr 28 '17 at 6:26
• can you just look at the code that i have posted ? .i think you can get it easily . – satyajeet jha Apr 28 '17 at 6:28

The sum-of-divisors function $\sigma(n)$ is a multiplicative function, because in terms of Dirichlet's convolutions it is simply $\mathbb{1}*\mathbb{1}$. We may notice that if $p$ is an odd prime number $$\sigma(p^k) = 1+p+\ldots+p^k$$ has the same parity of $k+1$, and if $p=2$ then $\sigma(p^k)$ is odd. In particular:

$\sigma(n)$ is odd if and only if $n$ is a number of the form $2^m(2k+1)^2$.