# Is there a formula to calculate the sum of all proper divisors of a number?

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

If the prime factorization of $$nn$$ is $$n=∏kpakk,n=\prod_k p_k^{a_k},$$ where the $$pkp_k$$ are the distinct prime factors and the $$aka_k$$ are the positive integer exponents, the sum of all the positive integer factors is $$∏k(ak∑i=0pik).\prod_k\left(\sum_{i=0}^{a_k}p_k^i\right).$$

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

For proper factors, subtract $$nn$$ 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.