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 don't need to list all proper divisors, I just want to get its sum. Because for a small number, checking all proper divisors and adding them up is not a big deal. However, for a large number, this would run extremely slow. Any idea?

Thanks,
Chan Nguyen

share|improve this question

4 Answers 4

up vote 23 down vote accepted

If the prime factorization of $n$ is $$n=\prod_k p_k^{a_k}$$ where the $p_k$ are the distinct prime factors and the $a_k$ are the positive integer exponents, the sum of all the positive integer factors is $$\prod_k\left(\sum_{i=0}^{a_k}p_k^i\right).$$

For example, the sum of all of the factors of $120=2^3\cdot3\cdot5$ is $$(1+2+2^2+2^3)(1+3)(1+5)=15\cdot4\cdot6=360.$$

For proper factors, subtract $n$ from this sum. This may or may not be faster, depending on the number and how you'd get the prime factorization, but this is the typical technique for high school contest problems of this sort.

share|improve this answer
    
@Issac: Thank you! In fact, I thought of prime factorization, but the algorithm for factorization is not fast too. –  Chan Feb 18 '11 at 23:10
    
The sum of divisors can also be written using $\sum_{i=0}^{a_k}p_k^i = (p_k^{a_k + 1})/(p_k - 1)$ for the individual factors, as may be seen from the PlanetMath article: planetmath.org/encyclopedia/FormulaForSumOfDivisors.html –  hardmath Feb 18 '11 at 23:18
4  
@hardmath: Absolutely—each sum is the sum of a geometric series (though I think it should probably be $$\prod_k\left(\sum_{i=0}^{a_k}p_k^i\right)=\prod_k\frac{p_k^{a_k + 1}-1}{p_k - 1}$$ (add $-1$ in the numerator). –  Isaac Feb 18 '11 at 23:41
    
Yes, I miss preview mode in comments... –  hardmath Feb 19 '11 at 21:19

Just because it is interesting:

There is actually a (less known) recursive formula for calculating $\sigma(n)$, the sum of the divisors of $n$.

$$\sigma(n) = \sigma(n-1) + \sigma(n-2) - \sigma(n-5) - \sigma(n-7) + \sigma(n-12) +\sigma(n-15) + ..$$ Here $1,2,5,7,...$ is the sequence of generalized pentagonal numbers $\frac{3n^2-n}{2}$ for $n = 1,-1,2,-2,...$ and the signs are repetitions of $1,1,-1,-1$. The summation continues until you try to calculate $\sigma$ of something negative. However, if $\sigma(0)$ occurs in the summation (this happens precisely when $n$ is a generalized pentagonal number), it should be replaced by $n$ itself. In other words $$ \sigma(n) = \sum_{i\in \mathbb Z_0} (-1)^i\left( \sigma(n - \tfrac{3i^2-i}{2}) + \delta(n,\tfrac{3i^2-i}{2}) \right), $$ where we set $\sigma(i) = 0$ for $i\leq 0$ and $\delta(\cdot,\cdot)$ is the Kronecker delta.

Note that calculating $\sigma(n)$ requires $\sigma(n-1)$ already, therefore its complexity is at least $\mathcal O(n)$, which makes it kind of useless for practical purposes. Note however the lack of reference to divisibility in this formula, which makes it a bit miraculous and therefore worth mentioning.

Here's a reference to the Euler's paper from 1751.

share|improve this answer
    
Many thanks for a great information. Although I don't understand it completely now, I will go back to it when I'm ready. –  Chan Feb 19 '11 at 4:58
    
Is the formula correct? I get a negative sign for i=1 in your sum, and $\sigma(n-\frac{3 1^2 - 1}{2})$ has a positive sign in your first equation. Most likely, I made a mistake... (I tried it by hand using n=6). –  Unapiedra Oct 11 '13 at 17:25
    
"it should be replaced by $n$ itself". So do that: $\delta(...) n$, also I find that it should be $(-1)^{i+1}$. Doing this gives me correct result for all my test cases. –  Unapiedra Oct 11 '13 at 23:08

If you want numerical values then the calculator at the site below will list all divisors of a given positive integer, the number of divisors and their sum. It also has links to calculators for other number theory functions such as Euler's totient function.

http://www.javascripter.net/math/calculators/divisorscalculator.htm

share|improve this answer

If No = a^p × b^q × c^r × ... then total divisors = (p + 1)(q + 1)(r + 1) ...

sum of divisors = a^(p+1)/(a–1) × b^(q+1)/(b–1) × c^(r+1)/(c–1)

e.g. divisors of 8064 8064 = 2^7 × 3^2 × 7^1

total number of divisors = (7+1)(2+1)(1+1) = 48

sum of divisors = [2^(7+1) –1]/(2–1) × [3^(2+1) –1]/(3–1) × [7^(1+1) –1]/(7–1)

= 255 × 7 × 8 = 26520

share|improve this answer

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.