5 Best Ways to Find Common Fractions Between Min and Max with Python

💡 Problem Formulation: Finding common fractions between a defined minimum and maximum value can be a challenging task if constraints are involved. For instance, given a range between 1/4 and 3/4, with a constraint where the denominator cannot exceed 10, one might seek to find all fractions within this range that meet the criteria. The desired output would be a list of fractions, such as [1/4, 1/3, 1/2, 2/3, 3/4], that fall within the specified bounds and respect the given constraint.

Method 1: Brute Force Enumeration

This method involves iterating over all possible numerators and denominators within the given constraints and checking if the formed fraction is within the specified bounds. This is simple to implement but may not be efficient for large ranges or tight constraints.

Here’s an example:

from fractions import Fraction

def find_common_fractions(min_val, max_val, max_denom):
    common_fractions = []
    for denom in range(1, max_denom + 1):
        for num in range(1, denom):
            frac = Fraction(num, denom)
            if min_val <= frac < max_val:
                common_fractions.append(frac)
    return common_fractions

fractions_list = find_common_fractions(Fraction(1, 4), Fraction(3, 4), 10)
print(fractions_list)

Output:

[Fraction(1, 4), Fraction(1, 3), Fraction(1, 2), Fraction(2, 3), Fraction(3, 4)]

In this code snippet, we define a function find_common_fractions that accepts minimum and maximum values, as well as the maximum allowed denominator. It goes through all potential fractions and adds valid ones to a list. Though straightforward, it is not the most optimal approach for larger ranges due to the computational workload required.

Method 2: Using Generators

The generator method allows for a more memory-efficient approach, creating an iterator that yields each valid fraction as it is found. This is particularly beneficial when dealing with large sets of fractions where storing them all in memory at once would be impractical.

Here’s an example:

def generate_common_fractions(min_val, max_val, max_denom):
    for denom in range(1, max_denom + 1):
        for num in range(1, denom):
            frac = Fraction(num, denom)
            if min_val <= frac < max_val:
                yield frac

for frac in generate_common_fractions(Fraction(1, 4), Fraction(3, 4), 10):
    print(frac)

Output:

1/4
1/3
1/2
2/3
3/4

The function generate_common_fractions is a generator that yields each valid fraction. This snippet illustrates how to iterate over the generator and print each fraction. Generators are efficient in memory usage, which makes this method scalable for larger datasets, but it might have a slower execution time due to on-the-fly calculations.

Method 3: Mathematical Optimization

This method applies mathematical insights to reduce the search space. By recognizing patterns in the fractions, such as equivalent forms and simplifiable numbers, one can skip redundant checks and directly enumerate only the necessary fractions.

Here’s an example:

import math

def optimized_common_fractions(min_val, max_val, max_denom):
    common_fractions = []
    for denom in range(1, max_denom + 1):
        start_num = math.ceil(denom * min_val)
        end_num = math.floor(denom * max_val)
        for num in range(start_num, end_num + 1):
            frac = Fraction(num, denom).limit_denominator(max_denom)
            common_fractions.append(frac)
    return list(set(common_fractions))

fractions_list = optimized_common_fractions(Fraction(1, 4), Fraction(3, 4), 10)
print(sorted(fractions_list))

Output:

[1/4, 1/3, 1/2, 2/3, 3/4]

This function, optimized_common_fractions, leverages mathematical functions to constrain the range of numerators, thus avoiding the enumeration of invalid fractions. It further uses limit_denominator() to keep fractions within constraints and removes duplicates. This method is more efficient for ranges that map to a large number of potential fractions by limiting the iteration span.

Method 4: Utilizing Advanced Number Theory

Advanced number theory techniques, like the Farey sequence, can be applied to generate fractions in their simplest form between given bounds. This approach is optimal for theoretical and precise fraction generation, especially when the pattern of fractions is well-behaved within the bounds.

Here’s an example:

def farey_sequence(min_val, max_val, max_denom):
    a, b, c, d = 0, 1, 1, max_denom
    common_fractions = []
    while c <= max_denom:
        if a/b >= min_val:
            common_fractions.append(Fraction(a, b))
        k = (max_denom + b)//d
        a, b, c, d = c, d, k*c - a, k*d - b
    return common_fractions

fractions_list = farey_sequence(Fraction(1, 4), Fraction(3, 4), 10)
print(sorted(fractions_list))

Output:

[1/4, 1/3, 1/2, 2/3, 3/4]

The farey_sequence function generates fractions in ascending order between two bounds. It employs a mathematical approach where fractions are determined by linear combinations of existing terms. This method is incredibly efficient as it only generates unique, simplified fractions, though it might be complex for those not familiar with advanced mathematical concepts.

Bonus One-Liner Method 5: Using List Comprehensions

For minimalists, Python’s list comprehension can be utilized to produce a compact, one-liner solution. This combines the enumeration and filtering steps in a concise expression that is straightforward to read and write for small-scale problems.

Here’s an example:

fractions_list = sorted({Fraction(n, d) for d in range(1, 11) for n in range(1, d) if Fraction(1, 4) <= Fraction(n, d) <= Fraction(3, 4)})
print(fractions_list)

Output:

[1/4, 1/3, 1/2, 2/3, 3/4]

This one-liner uses a set comprehension to generate all possible fractions within a given range while ensuring uniqueness. Then it sorts the set into a list to produce the final output. It is an elegant solution that is easily understandable, but it may not scale well with larger datasets or more complex constraints.

Summary/Discussion

• Method 1: Brute Force Enumeration. Simple to understand and implement. Not efficient for large datasets.
• Method 2: Using Generators. Memory-efficient, suitable for large datasets. May have slower runtime due to on-the-fly calculations.
• Method 3: Mathematical Optimization. More efficient by reducing redundancy. Still might require manual optimization for best performance.
• Method 4: Advanced Number Theory. Highly efficient and precise. Can be complex and less approachable for beginners.
• Method 5: List Comprehensions. Compact and Pythonic. Not suitable for handling large datasets or complex constraints.