5 Best Ways to Check If the Sum of Divisors of Two Numbers Are the Same in Python

by

💡 Problem Formulation: We want to discern whether two given integers have the same sum of their proper divisors. Given two integers, for example, 15 and 9, we seek to determine if the sum of the divisors (excluding the number itself) of each are equal. If so, the output should indicate a boolean True; otherwise False.

Method 1: Brute Force

This method entails iterating over all possible divisors of each number and accumulating their sum to compare at the end. The function sum_of_divisors() computes the sum of divisors for a single number, and then we compare the results for both numbers.

Here’s an example:

def sum_of_divisors(n):
    divisors_sum = 0
    for i in range(1, n):
        if n % i == 0:
            divisors_sum += i
    return divisors_sum

num1 = 15
num2 = 9

# Compare the sum of divisors
print(sum_of_divisors(num1) == sum_of_divisors(num2))

Output:

False

This code snippet defines the sum_of_divisors function that computes the sum of all divisors for a given number by iterating through all numbers less than the given number. It then calculates and compares the sums for both num1 and num2.

Method 2: Using List Comprehension

This method leverages Python’s list comprehension and the built-in sum() function to condense the logic into a single line. This approach is more pythonic and may often be more readable.

Here’s an example:

sum_of_divisors = lambda n: sum([i for i in range(1, n) if n % i == 0])

num1 = 15
num2 = 9

# Compare the sum of divisors
print(sum_of_divisors(num1) == sum_of_divisors(num2))

Output:

False

In this snippet, sum_of_divisors is a lambda function that uses a list comprehension to generate a list of divisors and then sums them up. It simplifies the process of calculating the sum of divisors and makes the comparison concise.

Method 3: Optimized Divisor Sum

This approach optimizes the divisor sum calculation by only checking for divisors up to the square root of the number, reducing the number of iterations and thus improving performance.

Here’s an example:

import math

def optimized_sum_of_divisors(n):
    divisors_sum = 1
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            divisors_sum += i + (n // i if i != n // i else 0)
    return divisors_sum

num1 = 15
num2 = 9

print(optimized_sum_of_divisors(num1) == optimized_sum_of_divisors(num2))

Output:

False

The optimized_sum_of_divisors function reduces the number of iterations by looping only up to the square root. If a divisor is found, it adds both the divisor and the corresponding quotient to the sum, ensuring that we do not miss any divisors.

Method 4: Sieve for Multiple Queries

For cases where we need to frequently check for the sum of divisors of different numbers, a Sieve-like approach can be used to precalculate sums for a range of numbers.

Here’s an example:

def sieve_sum_of_divisors(max_n):
    divisor_sums = [0] * (max_n + 1)
    for i in range(1, max_n + 1):
        for j in range(i * 2, max_n + 1, i):
            divisor_sums[j] += i
    return divisor_sums

max_num = max(15, 9)
divisor_sums = sieve_sum_of_divisors(max_num)

print(divisor_sums[15] == divisor_sums[9])

Output:

False

This snippet creates a list called divisor_sums which holds the sum of divisors for each number up to max_num. It uses a nested loop authoring a Sieve-like algorithm that populates the sums efficiently, particularly useful for multiple queries.

Bonus One-Liner Method 5: Using sum() and range() in a Lambda

A compact one-liner uses a lambda function with sum and range to compute the divisor sum for comparison. It’s a more succinct version of list comprehension.

Here’s an example:

check_divisor_sums = lambda x, y: sum(i for i in range(1, x) if x % i == 0) == sum(i for i in range(1, y) if y % i == 0)

num1, num2 = 15, 9
print(check_divisor_sums(num1, num2))

Output:

False

The one-liner check_divisor_sums lambda function is a concise and functional way to directly compare the sum of divisors for two numbers without the need for an auxiliary function.

Summary/Discussion

  • Method 1: Brute Force. Straightforward and easy to understand. Inefficient for large numbers.
  • Method 2: Using List Comprehension. Concise and pythonic. Still has inefficiencies similar to brute force for large numbers.
  • Method 3: Optimized Divisor Sum. More efficient, especially for larger numbers. Requires a bit more complex logic to grasp.
  • Method 4: Sieve for Multiple Queries. Extremely efficient for repeated queries. Requires additional memory and initial setup time.
  • Method 5: Using sum() and range() in a Lambda. Elegantly compact. Readability might be an issue for beginners.