Well, we don’t need to sum up all those divisors if you encounter a question that requires you to find out the sum of divisors of an integer. Instead, let’s find out the more efficient method in this article. Note that σ(number) means the sum of divisors of that number.
The Factorization
Firstly, you have to find out the factorization of the number. Unfortunately, this is also the most challenging part if it involves large integers. That’s because you may not know if the “suspected prime” (like 15811 or 18643) is truly prime before pressing lots of keys on your calculator. However, this is easier to be done if the integer doesn’t have large prime factors (like 27720 or 43560).
To factorize a number, you should eliminate the obvious prime factors using divisibility checks. For instance, if a number ends in 2, 4, 6, 8, or 0, you should divide the integer by two. If the sum of the digits of the number is divisible by 3, divide the number by 3. Jot down the prime factors and do so until you are unsure whether an integer is prime or not. The more primes you remember, the faster the process becomes.
In the end, if you want to make sure the remaining integer is prime, you should divide it by all primes below the square root of that integer. (Note: If the square root is an integer, it is a perfect square and not a prime).
Obtaining the Sum of Divisors
If the integer turns out to be a prime or a prime power, we will have to go back to the ineffective method and list and sum up all the factors. Fortunately, the sum of divisors of a prime number is one plus the number, so it is very easy to figure out.
For squarefree composite numbers, you just need to find out the product of every prime factor plus one. For instance, 3 * 7 * 11 = 231. Therefore, its sum of divisors is 4 * 8 * 12 = 384. 2002 is 2 * 7 * 11 * 13, so σ(2002) = 3 * 8 * 12 * 14 = 4032.
We have to calculate prime powers distinctly. This means you should take those as primes where they really aren’t. Instead of multiplying the prime power plus one, we have to figure out its sum of divisors before taking this into your parameters. For example, 52 * 11 = 275. As a result, its sum of divisors is 31 (σ(25)) * 12 = 372. 840 is 23 * 3 * 5 * 7, so its divisors sum up to 15 * 4 * 6 * 8 = 2880.
Perfect Numbers
Through this method, we can also describe the relationship between Mersenne primes and perfect numbers and why the latter is a subsequence of triangular numbers.
2(p-1) * 2p – 1 is always perfect if both p and 2p – 1 are prime. Take 496 as an example, whose p is 5. It is divisible by 16 but not 32, which means that 31 is multiplied by another number in σ(496). You can see that 496 is divisible by 31, and σ(31) = 32. That means σ(496) = 992, which equals to 496 when it is halved. This works on all other perfect numbers of this type, and the only difference is that the prime is different.
The proof is simple. Just read the previous paragraph again, and you will realize that a twice a perfect number is the product of two consecutive integers. What’s more, the “n” in this formula is the closely associated Mersenne prime when the solution is a perfect number, and the reason is clearly observable through the formula that is satisfied by a perfect number.
Bonus: The Number of Divisors
The prime factorization can also be used to calculate its number of divisors, as explained in this article. Instead of looking at the primes, we only have to focus on powers. All prime factors of squarefree numbers are raised to the power of one, so their number of divisors must be a power of two. For instance, 2 * 3 * 7 * 11 = 462, so it has 2 * 2 * 2 * 2 = 16 divisors
We have to multiply n+1 to the current number when the prime factor is raised to the power of n. For example, 26 * 3 * 5 = 960. Consequently, it has 7 * 2 * 2 = 28 divisors. 23 * 33 * 5 = 1080, so it has 4 * 4 * 2 = 32 factors.
Quiz
Conclusion
The next time you are asked to obtain the sum and number of divisors of an integer without a program, make sure you use this method if you want to do it efficiently! If we missed any important points or wrongly mentioned them, please leave them in the comments below so that we can improve the article.