Counting Fractions in a Range¶

As mentioned in problem 71, it's easy to compute the next value to appear between two neighbors in a Farey sequence by computing their mediant. Using this fact, we can can repeatedly calculate mediants to get every value between two neighbors in the sequence, stopping when the denominators get too big - in fact, for this problem, we only need to calculate the denominators.

This essentially amounts to a depth-first search of the Stern-Brocot tree - check it out if you'd like a visualization.

Theoretically, we could count using a recursive function, but Python will hit its recursion limit if we try to use it to solve this problem.

In [1]:
def stern_brocot_count(d, low, high):
    middle = low + high
    if middle > d:
        return 0
    
    return 1 + stern_brocot_count(d, low, middle) + stern_brocot_count(d, middle, high)

Instead, we'll solve the problem with the same principle, just implemented with a stack.

In [2]:
d = 12000
total = 0
stack = [(3, 2)]
while stack != []:
    low, high = stack.pop()
    middle = low + high
    
    if middle > d:
        continue
    total += 1
    
    stack.extend([(low, middle), (middle, high)])
    
total
Out[2]:
7295372

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.