Calculating the Probability of an Even Perfect Square Divisor in Python

💡 Problem Formulation: The task at hand is to devise a Python program that can compute the probability that a proper divisor of a given positive integer n is an even perfect square. For example, if n = 36, proper divisors such as 4 and 16 are even perfect squares. The desired output is the probability value expressed as a fraction or a float.

Method 1: Brute Force Search

This method involves iterating over all the proper divisors of a number n to check if they are even perfect squares. It counts the occurrences and divides this count by the total number of proper divisors to calculate the probability.

Here’s an example:

import math

def is_even_perfect_square(x):
    root = math.sqrt(x)
    return root.is_integer() and x % 2 == 0

def probability_even_square_divisor(n):
    even_perfect_square_divisors = sum(is_even_perfect_square(i) for i in range(1, n) if n % i == 0)
    total_divisors = sum(1 for i in range(1, n) if n % i == 0)
    return even_perfect_square_divisors / total_divisors if total_divisors else 0

# Example
n = 36
print(probability_even_square_divisor(n))

The output will be:

0.2

In the provided code snippet, we define a helper function is_even_perfect_square that determines if a number is an even perfect square. The function probability_even_square_divisor uses this helper to count appropriate divisors and calculate the probability.

Method 2: Optimized Divisor Search

Instead of checking all integers up to n, this method optimizes by only inspecting divisors up to the square root of n, doubling the count for non-square divisors, as each gives rise to a pair of divisors.

Here’s an example:

import math

def probability_even_square_divisor(n):
    count_even_perfect_squares = 0
    count_divisors = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            # Count divisors i and n/i if i*i isn't n
            count_divisors += 1 if i * i == n else 2
            if i % 2 == 0 and math.sqrt(i).is_integer():
                count_even_perfect_squares += 1
            if (n // i) % 2 == 0 and math.sqrt(n // i).is_integer():
                count_even_perfect_squares += 1
    return count_even_perfect_squares / count_divisors if count_divisors else 0

# Example
n = 36
print(probability_even_square_divisor(n))

The output will be:

0.2

This method is more efficient as it iterates only up to sqrt(n) and accounts for both divisors in the pair i and n/i. It keeps a tally of even perfect square divisors and total divisors to compute the probability.

Method 3: Functional Style with filter and map

A functional approach can be employed using Python’s filter and map functions to isolate the even perfect square divisors, coupled with the use of generator expressions for performance.

Here’s an example:

def probability_even_square_divisor(n):
    divisors = (i for i in range(1, n) if n % i == 0)
    even_squares = filter(lambda x: x % 2 == 0 and math.sqrt(x).is_integer(), divisors)
    total_divisors = sum(1 for _ in divisors)
    even_square_count = sum(1 for _ in even_squares)
    return even_square_count / total_divisors if total_divisors else 0

# Example
n = 36
print(probability_even_square_divisor(n))

The output will be:

0.2

The code defines a single function probability_even_square_divisor that computes the total number of divisors and the number of even perfect square divisors using filter and generator expressions. It returns the probability as a float.

Method 4: Using Set Comprehension and Intersection

This novel method involves generating two sets using comprehension: one of even perfect squares up to n and one of divisors of n

. Then the intersection of these sets gives the desired divisors which can be used to calculate the probability.

Here’s an example:

def probability_even_square_divisor(n):
    squares = {i*i for i in range(1, int(n**0.5)+1) if (i*i) % 2 == 0}
    divisors = {i for i in range(1, n) if n % i == 0}
    even_square_divisors = squares.intersection(divisors)
    return len(even_square_divisors) / len(divisors) if divisors else 0

# Example
n = 36
print(probability_even_square_divisor(n))

The output will be:

0.2

The approach uses set comprehension to create sets for even squares and divisors, then applies set intersection to identify even perfect square divisors. The ratio of the size of this intersection to the size of the divisors set yields the probability.

Bonus One-Liner Method 5: Utilizing NumPy for Array Operations

This compact method leverages the power of NumPy for array operations, identifying even perfect square divisors in a vectorized manner.

Here’s an example:

import numpy as np

def probability_even_square_divisor(n):
    divisors = np.arange(1, n) [n % np.arange(1, n) == 0]
    return np.mean(np.isin(divisors, np.arange(2, n, 2)**2))

# Example
n = 36
print(probability_even_square_divisor(n))

The output will be:

0.2

The one-liner utilizes NumPy’s capabilities to rapidly filter divisors of n and compute the mean of a Boolean array that indicates whether each divisor is an even perfect square, hence providing the probability.

Summary/Discussion

• Method 1: Brute Force Search. Thorough but can be slow for large n. Easy to understand and implement.
• Method 2: Optimized Divisor Search. Much more efficient than brute force, especially for larger numbers. Slightly more complex to understand.
• Method 3: Functional Style. Elegant and readable with a performance edge due to lazy evaluation. May be less familiar to those not comfortable with functional programming techniques.
• Method 4: Set Comprehension and Intersection. Creative and efficient use of set operations. May consume more memory with set creation.
• Method 5: NumPy One-Liner. Extremely concise and leverages vectorized operations for performance. Dependencies on the NumPy library could be seen as a disadvantage for simple tasks.