Project Euler Solution 73: Counting fractions in a range

Project Euler Problem 73: Counting fractions in a range continues with fractions.

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

This problem can be solved with brute force like this, using the fraction reduction from Solution 71: Ordered fractions:

def solution_all_fractions() -> None:
    fractions = set()
    for denominator in tqdm(range(1, 12_000 + 1)):
        for numerator in range(1, denominator):
            fractions.add(reduce_fraction(numerator, denominator))
    return len(fractions)

It takes around 15 seconds and requires 1.2 GB of memory. This is not a problem on a modern machine, though it would have been a problem in 2004 when this problem came out.

We can improve on this a bit by realizing that we only want to take a look at the fractions which are already reduced. If we only count those, then we don't need to keep track of them all. We directly use the greatest common denominator from Solution 33: Digit cancelling fractions.

def solution_count_reduced() -> int:
    result = 0
    for denominator in tqdm(range(1, 12_000 + 1)):
        for numerator in range(1, denominator):
            if 1 / 3 < numerator / denominator < 1 / 2:
                if greatest_common_denominator(numerator, denominator) == 1:
                    result += 1
    return result

This runs in 7715.732 ms and gets by with just 15 MB of memory. Virtually all of that is for the Python interpreter. This solution is much better already.

We can try to use the Farey sequence from Solution 72: Counting fractions and just take the ones which are within the limits:

def solution_farey() -> int:
    result = 0
    for numerator, denominator in farey_sequence(12_000):
        if 1 / 3 < numerator / denominator < 1 / 2:
            result += 1
    return result

This takes a bit longer, namely 10 s. So that is not an improvement. The division isn't a problem, reformulating the condition as denominator < numerator * 3 and 2 * numerator < denominator is not any faster.

The supplemental material to the problem on the site shows very elaborate ways of making this faster. They seem to be a bit above my number theory skills, so I'll not try to copy their thoughts here but it leave it to you to find the supplemental materials.