Project Euler Solution 71: Ordered fractions

Project Euler Problem 71: Ordered fractions brings us back to something more elementary, basic 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 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

If we would just try to list all fractions, we would have 10⁶ numerators and 10⁶ denominators to check. We would throw away around half of them as they are larger than 1. And then we would reduce the fractions. This would still be a list which is way too long to generate in memory. We need to find something better.

Let us express the solution in term of a function that we can test with the example. We give it a fraction and a limit for the denominator and expect to get the next closest fraction out.

def test_find_next_smaller_fraction() -> None:
    assert find_next_smaller_fraction((3, 7), 8) == (2, 5)

In order to implement this, we will go through all the denominators and find the numerator via bisection. Then we cancel the fraction using the greatest common denominator from Solution 33: Digit cancelling fractions. At the end we collect all of them and take the minimum.

def find_next_smaller_fraction(
    target: tuple[int, int], ceiling: int
) -> tuple[int, int]:
    target_numerator, target_denominator = target
    candidates = []
    for denominator in range(1, ceiling + 1):
        numerator = bisect_numerator(target, denominator)
        if numerator * target_denominator < target_numerator * denominator:
            numerator, denominator = reduce_fraction(numerator, denominator)
            candidates.append((numerator / denominator, numerator, denominator))
    m = max(candidates)
    return m[1:]

For the bisection we can write a test as well:

def test_bisect_numerator() -> None:
    assert bisect_numerator((3, 7), 5) == 2

The implementation is just a plain bisection.

def bisect_numerator(target: tuple[int, int], denominator: int) -> int:
    target_numerator, target_denominator = target
    lower = 0
    upper = denominator * target_numerator // target_denominator
    while lower < upper - 1:
        middle = (lower + upper) // 2 + 1
        if middle * target_denominator > target_numerator * denominator:
            upper = middle
        else:
            lower = middle
    return lower

For the cancellation of fractions I have pulled out a function to do that.

def reduce_fraction(numerator: int, denominator: int) -> tuple[int, int]:
    gcd = greatest_common_denominator(numerator, denominator)
    numerator //= gcd
    denominator //= gcd
    return numerator, denominator

The solution now is just an application of that function:

def solution() -> int:
    return find_next_smaller_fraction((3, 7), 1_000_000)[0]

This finds the right solution in 2.8 ms, so that would be acceptable.

Can we do better?

It seems that we might be able to do better here. Instead of trying out all the denominators, perhaps we can directly skip to the answer?

Let us take a look at the example. There we have d ≤ 8 given and we want to find the fraction smaller than 3/7. The solution is 2/5. The difference between these two numbers is 1/35.

Looking at the solution to the full problem, 428,570/999,997 and find that the difference is 1/6,999,979. This number is almost seven million and it seems sensible that it has this value. When we have d ≤ 1,000,000, the maximum distance between the individual fractions can be 1/1,000,000. This means that we only have to search in this tiny interval.

The fractions could be very close, but there is a limit to that as well. We know that the denominator has to be below that ceiling. So when we cancel it, it needs to have a d below that ceiling. This means that the denominator of the difference can at most have be smallest common multiple of 7 and the denominator that we choose. It seems sensible to start with d = 1,000,000 and reduce it from there.

We therefore take denominators for the difference. Then we extend the fraction 3/7 by that denominator and subtract one from the numerator, which is essentially subtracting 1/x from 3/7. We then reduce the fraction again. If the result has a denominator below 1,000,000, that is our solution.

def solution_faster() -> int:
    ceiling = 1_000_000
    for difference_denominator in reversed(range(ceiling)):
        numerator = 3 * difference_denominator
        denominator = 7 * difference_denominator
        numerator -= 1
        numerator, denominator = reduce_fraction(numerator, denominator)
        if denominator <= ceiling:
            return numerator, denominator

This finds the solution in 2 µs, which is much more satisfying.