Finding Perfect Squares with Digital Sum Less Than 10 in Python

by

💡 Problem Formulation: We are tasked with identifying all numbers within a given range that are not only perfect squares but also have a sum of all their digits that totals less than 10. For instance, if our range is 1-100, the number 81 is a perfect square (9×9) and its digit sum (8+1) is 9, which is less than 10 – thus, it meets our criteria.

Method 1: Brute Force Approach

This method involves iterating through each number in the given range, checking if it is a perfect square, and then calculating the sum of its digits to see if it is less than 10. While this method is simple and straightforward, it is not the most efficient for large ranges due to its O(n) complexity.

Here’s an example:

def is_perfect_square(n):
    root = int(n**0.5)
    return n == root * root

def digit_sum_less_than_ten(n):
    return sum(map(int, str(n))) < 10

def find_perfect_squares_with_digit_sum(range_start, range_end):
    return [x for x in range(range_start, range_end + 1) if is_perfect_square(x) and digit_sum_less_than_ten(x)]

# Using the function
print(find_perfect_squares_with_digit_sum(1, 100))

Output:

[1, 4, 9, 16, 81]

This code snippet defines two functions: is_perfect_square() checks if a given integer is a perfect square, and digit_sum_less_than_ten() returns True if the sum of digits of an integer is less than 10. The main function find_perfect_squares_with_digit_sum() generates a list of numbers in the specified range that are perfect squares with digit sums less than 10.

Method 2: Use of List Comprehension

List comprehension in Python allows for a more concise and readable form of the Brute Force Approach. It combines the checks for a perfect square and the digit sum within a single line of code, making it more ‘Pythonic’ albeit with the same computational complexity.

Here’s an example:

def perfect_squares_with_digit_sum(range_start, range_end):
    return [x for x in range(range_start, range_end + 1)
            if x == int(x**0.5)**2 and sum(int(digit) for digit in str(x)) < 10]

# Example execution
print(perfect_squares_with_digit_sum(1, 100))

Output:

[1, 4, 9, 16, 81]

This code snippet introduces a list comprehension that performs both the perfect square and the digit sum tests in a single line, outputting numbers within the range that satisfy both conditions. The condition int(x**0.5)**2 == x confirms that ‘x’ is a perfect square by comparing it to its squared integer root.

Method 3: Using Math Functions for Efficiency

By incorporating Python’s math module, it is possible to improve the effectiveness of the square root check. By replacing int casting with math.isqrt(), we gain a minor performance increase for the perfect square test.

Here’s an example:

import math

def perfect_squares_with_digit_sum_math(range_start, range_end):
    return [x for x in range(range_start, range_end + 1)
            if x == math.isqrt(x)**2 and sum(int(digit) for digit in str(x)) < 10]

# Example execution
print(perfect_squares_with_digit_sum_math(1, 100))

Output:

[1, 4, 9, 16, 81]

The math.isqrt(x) function in this code snippet is used instead of computing the square root and casting it to an integer, which enhances the check for a perfect square. It’s a more elegant and potentially faster method for checking perfect squares, specifically in large-range scenarios.

Method 4: Optimizing the Range

Instead of checking every number in the range, we can optimize by only considering numbers whose square roots are integers – immediately filtering out non-perfect squares. This drastically reduces the amount of iterations required.

Here’s an example:

def optimized_perfect_squares_with_digit_sum(range_start, range_end):
    return [x*x for x in range(int(math.ceil(range_start**0.5)), int(math.floor(range_end**0.5)) + 1)
            if sum(int(digit) for digit in str(x*x)) < 10]

# Example usage
print(optimized_perfect_squares_with_digit_sum(1, 100))

Output:

[1, 4, 9, 16, 81]

This snippet reduces the range to only include numbers that are the square of integers, starting from the ceiling of the square root of the start of the range and ending at the floor of the square root of the end of the range. This approach significantly lowers the number of iterations and operations needed to find the result.

Bonus One-Liner Method 5: Streamlined Comprehension

By streamlining the list comprehension, we create a one-liner method that combines the optimized range check with the perfect square and digit sum conditions. This is the most condensed form of all the other methods, providing the same results efficiently.

Here’s an example:

print([x*x for x in range(int(math.ceil(1**0.5)), int(math.floor(100**0.5)) + 1) if sum(int(digit) for digit in str(x*x)) < 10])

Output:

[1, 4, 9, 16, 81]

This one-liner is the epitome of Python’s expressive power, packing all the previous method’s calculations and conditions into a single concise and readable line of code, following the Pythonic principle of ‘Simple is better than complex.’

Summary/Discussion

  • Method 1: Brute Force Approach. Straightforward implementation. Not efficient for large ranges.
  • Method 2: List Comprehension. Clean and readable. Maintains O(n) complexity.
  • Method 3: Using Math Functions. Minor performance optimization. Still not ideal for very large ranges.
  • Method 4: Optimizing the Range. Substantial performance increase by reducing iterations. Requires mathematical understanding of squares.
  • Method 5: Streamlined Comprehension. Combines the efficiency of Method 4 with the elegance of a one-liner. Ideal for Python enthusiasts who value conciseness.