0
$\begingroup$

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;
    }
$\endgroup$
2
$\begingroup$

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);
}
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @the value of n can be as large as 10^15 $\endgroup$ – satyajeet jha Apr 28 '17 at 6:26
  • $\begingroup$ can you just look at the code that i have posted ? .i think you can get it easily . $\endgroup$ – satyajeet jha Apr 28 '17 at 6:28
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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