Simplified Fractions: GCD-Based Enumeration

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less than or equal to n. You can return the answer in any order. A fraction numerator/denominator is simplified if there is no integer other than 1 that divides both the numerator and denominator.

This is LeetCode 1447: Simplified Fractions, and it is a clean introduction to GCD-based filtering. The pattern of enumerating candidates and keeping only those that pass a number-theoretic test shows up across many math problems.

Why this problem matters

At first glance, generating fractions seems like a pure enumeration exercise. Loop through denominators, loop through numerators, collect them all. But the twist is the "simplified" requirement. You only want fractions in their lowest terms, which means you need a way to test whether a fraction is already fully reduced.

That test is the greatest common divisor (GCD). A fraction a/b is in simplest form when gcd(a, b) == 1. This connects a basic enumeration problem to one of the oldest algorithms in mathematics: Euclid's algorithm. Once you see this connection, the solution writes itself.

The GCD filtering pattern generalizes well. Problems involving coprime pairs, Euler's totient function, and modular arithmetic all rely on the same core idea: check whether two numbers share any factors, and branch based on the result.

The key insight

A fraction numerator/denominator is already in its simplest form when gcd(numerator, denominator) == 1. If the GCD is greater than 1, both values share a common factor, meaning the fraction can be reduced further, and some other fraction with a smaller denominator already represents the same value. So you skip it.

This means the algorithm is: enumerate every possible numerator/denominator pair where 1 <= numerator < denominator <= n, and keep only the pairs where the GCD equals 1.

The solution

from math import gcd

def simplified_fractions(n: int) -> list[str]:
    result = []
    for denom in range(2, n + 1):
        for numer in range(1, denom):
            if gcd(numer, denom) == 1:
                result.append(f"{numer}/{denom}")
    return result

The outer loop iterates through every possible denominator from 2 to n. We start at 2 because a denominator of 1 would make the fraction equal to numerator/1, which is at least 1 and therefore outside the range (0, 1).

The inner loop iterates through every possible numerator from 1 up to (but not including) the denominator. This guarantees the fraction is strictly between 0 and 1.

For each pair, we compute gcd(numer, denom). If it equals 1, the fraction is already in lowest terms and we format it as a string and add it to the result. If the GCD is anything other than 1, we skip it because a simpler version of that fraction already exists or will be generated with a smaller denominator.

Visual walkthrough

Let's trace through the algorithm for n = 4. We check each denominator from 2 to 4, test every numerator with the GCD, and build up the result list step by step.

The pattern is consistent across every step: enumerate numerators, check the GCD, keep or skip. The only fraction that gets filtered out in this example is 2/4, because gcd(2, 4) = 2. Every other fraction already has a GCD of 1 with its denominator.

Complexity analysis

Time is O(n^2 * log(n)). The nested loops iterate through all pairs (numer, denom) where 1 <= numer < denom <= n. The number of such pairs is roughly n^2 / 2. For each pair, we compute the GCD, which takes O(log(n)) time using Euclid's algorithm. Multiplying these together gives O(n^2 * log(n)).

Space is O(k) where k is the number of simplified fractions in the output. We only store the result list. The number of simplified fractions up to denominator n is related to Euler's totient function summed from 2 to n, which grows roughly as 3n^2 / pi^2.

The building blocks

1. GCD computation

from math import gcd

def are_coprime(a: int, b: int) -> bool:
    return gcd(a, b) == 1

The GCD tells you the largest number that divides both a and b. When it equals 1, the two numbers are coprime, meaning they share no common factors. This is the fundamental test used in this problem and in many number theory algorithms. Euclid's algorithm computes it by repeatedly replacing the larger number with the remainder of dividing the two, until the remainder is zero.

2. Proper fraction enumeration

def proper_fractions(n: int):
    for denom in range(2, n + 1):
        for numer in range(1, denom):
            yield (numer, denom)

This generator produces every proper fraction with a denominator up to n. The key constraint is numer < denom, which guarantees the fraction is between 0 and 1. You can layer any filter on top of this enumeration, whether it is GCD-based simplification, primality checks, or something else entirely. Separating the enumeration from the filtering makes the code modular and easy to adapt.

Edge cases

Before submitting, think through these scenarios:

• n = 1: No valid denominator exists (the smallest denominator is 2). Return an empty list.
• n = 2: Only one fraction: "1/2". The GCD of 1 and 2 is 1, so it passes.
• Prime denominator: When the denominator is prime, every numerator from 1 to denom - 1 produces a valid fraction because gcd(numer, prime) = 1 for all numer < prime.
• Power-of-two denominator: Many numerators will be filtered. For denominator 8, the even numerators 2, 4, and 6 all share a factor of 2 with 8.
• Large n: With n = 100, the output contains hundreds of fractions, but the algorithm still runs efficiently since each GCD call is O(log(n)).

From understanding to recall

The logic here is simple: two nested loops and a GCD check. But simplicity can be deceptive. Under time pressure, you might forget whether the inner loop starts at 0 or 1, whether it goes up to denom or denom - 1, or whether you check gcd == 1 or gcd > 1. These small details matter, and getting any one of them wrong produces incorrect output.

Spaced repetition drills these details into automatic recall. You practice writing the enumeration loop, the GCD check, and the string formatting from memory. After a few rounds, you do not need to think about the loop bounds or the GCD condition. They flow naturally from the pattern you have internalized.

The GCD filtering pattern also transfers to harder problems. Euler's totient function, Stern-Brocot trees, and Farey sequences all build on the same foundation. Mastering this building block here makes those problems approachable when you encounter them.

Related posts

• Count Primes - Another math enumeration problem using number theory
• Fraction to Recurring Decimal - Working with fractions and their decimal representations
• Palindrome Number - Math-based problem using digit manipulation

CodeBricks breaks Simplified Fractions into its GCD computation and proper fraction enumeration building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a math problem shows up in your interview, you do not think about it. You just write it.