aliquot sum Algorithm
The aliquot sum algorithm is a numerical method used to determine the sum of all proper divisors of a given number, excluding the number itself. Proper divisors are the factors of a number that are less than the number itself. The aliquot sum is also known as the sum of divisors or the sum of aliquot parts. This algorithm has applications in number theory, specifically in the study of abundant, perfect, and deficient numbers. An abundant number is a number for which the aliquot sum is greater than the number itself, a perfect number is a number for which the aliquot sum is equal to the number, and a deficient number is a number for which the aliquot sum is less than the number.
To implement the aliquot sum algorithm, one would typically start by finding all the factors of the given number. This can be achieved by iterating through numbers starting from 1 to the square root of the given number, and checking if the current number divides the given number without a remainder. If so, the current number is a factor, and the result of the division is also a factor. The sum of these factors is then calculated, excluding the given number itself. It is important to note that, in the case of perfect squares, the square root should only be counted once as a factor. The resulting sum represents the aliquot sum of the given number. This algorithm can be optimized by using more efficient techniques to find factors of a number, such as prime factorization or sieve methods.
def aliquot_sum(input_num: int) -> int:
"""
Finds the aliquot sum of an input integer, where the
aliquot sum of a number n is defined as the sum of all
natural numbers less than n that divide n evenly. For
example, the aliquot sum of 15 is 1 + 3 + 5 = 9. This is
a simple O(n) implementation.
@param input_num: a positive integer whose aliquot sum is to be found
@return: the aliquot sum of input_num, if input_num is positive.
Otherwise, raise a ValueError
Wikipedia Explanation: https://en.wikipedia.org/wiki/Aliquot_sum
>>> aliquot_sum(15)
9
>>> aliquot_sum(6)
6
>>> aliquot_sum(-1)
Traceback (most recent call last):
...
ValueError: Input must be positive
>>> aliquot_sum(0)
Traceback (most recent call last):
...
ValueError: Input must be positive
>>> aliquot_sum(1.6)
Traceback (most recent call last):
...
ValueError: Input must be an integer
>>> aliquot_sum(12)
16
>>> aliquot_sum(1)
0
>>> aliquot_sum(19)
1
"""
if not isinstance(input_num, int):
raise ValueError("Input must be an integer")
if input_num <= 0:
raise ValueError("Input must be positive")
return sum(divisor for divisor in range(1, input_num) if input_num % divisor == 0)
if __name__ == "__main__":
import doctest
doctest.testmod()
