An Improved Perfect Number Algorithm

Sometimes, the algorithm we think it’s the most optimal might not be the most optimal. As a matter of fact, it might not even be close to the most optimal one. In this post, we all will see an example of this kind of situation. Let’s learn about an advanced perfect number algorithm in Python.

What is a Perfect Number?

A perfect number is a natural number equal to the sum of its positive divisors excluding the number itself. For instance, 6 is a perfect number. Because divisors of 6 are 1, 2, 3, and 6 but we don’t count the number itself so we’re only gonna add up 1, 2, 3 which adds up to 6 (1+2+3).

The first elements of the Perfect Numbers sequence are 6, 28, 496, 8128, 33550336, 8589869056… and so on.

Primitive Algorithm for Finding Perfect Numbers

So, we know that perfect number definition. We can easily write an algorithm to solve perfect numbers. We will not care about its time complexity and efficiency.

A basic algorithm might be like this:

1. Take input from the user to set a limit to the maximum perfect number.
2. Create a for loop that iterates through 2 to user input.
3. Find the sum of divisors of every number in the loop excluding itself.
4. If the sum is equal to the number, return or print it.

If we code this in Python, the code would look like the following example:

def perfectNum(number):
	Sum = 0
	for i in range(2, number):
		if number % i == 0:
			Sum += i

	if Sum == number:
		return True
	return False

lim = int(input("Enter the limit: "))
perfectNums = []

for j in range(1, lim):
	if (perfectNum(j)):
		perfectNums.append(j)

print(*perfectNums)

What this code does is basically, listing every perfect number between 2 and the given number.

Now, we’ll try to upgrade it to a better perfect number algorithm. Our improved perfect number algorithm will be iterating through 2 and the square root of the given number. Therefore, the time complexity of the algorithm will be reduced from O(n) to O(sqrt(n)). If you don’t know what these “O” functions mean, please refer to an article that can inform you about Big O Notation.

Improved Perfect Number Algorithm

Before getting into coding, understand the logic. Why do we find the square root of the maximum number (given number from the user)?

If you take a look at positive whole divisors of a number, and list them ascending, you’ll be able to place this number’s square root right into the middle. It’ll always be in the middle. For instance, take a look at 24 and its divisors.

24 -> { 1, 2, 3, 4, sqrt(24) ≈ 4.89 , 6, 8, 12, 24 }

As you can see, the square root is in the center place. Thus, knowing half of its divisors will give us the other half. For example for 24, if we know that 4 is a divisor of it, we can find 6 by finding a solution of 24 / 4 and we won’t have to iterate through the rest of the number. So we can reduce our loop iterations to the square root of this number.

Since we understood the logic, let’s move to the code.

import math

def perfectNum(num):
    Sum = 1
    for i in range(2, math.ceil(num**0.5)):
        if (num % i == 0):
            Sum += i
            Sum += num // i

    return Sum == num and num != 1

lim = int(input("Enter The Max Limit: "))
perfectNums = []

for k in range(1, lim):
	perfectNum(k)
	if perfectNum(k) == True:
		perfectNums.append(k)

print(*perfectNums)

This new algorithm is 6.66 times for the input value of 1000, and roughly 36 times faster for 10000.

For those who want to learn more about this improved perfect number algorithm and the math behind it, you can watch my video about this topic.

Sources

Perfect Numbers: https://en.wikipedia.org/wiki/Perfect_number