Ordered 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.

Idea

Get the lower bound and upper bound of the numerators w.r.t a certain denominator.

Check all possible numerators and filter out $ HCF(n, d) \neq 1 $.

In [1]:
from math import gcd, floor, ceil
In [2]:
3/ 7
Out[2]:
0.42857142857142855
In [3]:
def get_bounds(d):
    d_digit_numbers = len(str(d))
    result_3_7 = 3 / 7
    intermedial = int(('{:.' + str(d_digit_numbers-1) + 'f}').format(result_3_7)[2:])
    return (intermedial-1) / pow(10, len(str(intermedial))), (intermedial+1) / pow(10, len(str(intermedial)))
In [4]:
get_bounds(10)
Out[4]:
(0.3, 0.5)
In [5]:
get_bounds(int(1e6))
Out[5]:
(0.42857, 0.428572)
In [6]:
def solve(d):
    max_result = (0, 0)
    lower_bound, upper_bound = get_bounds(int(d))
    for i in range(1, d+1):
        ns = range(ceil(lower_bound * i), floor(upper_bound * i)+1)
        reduced_proper_ns = list(filter(lambda n: gcd(i, n) == 1 and n / i < 3 / 7, ns))
        if reduced_proper_ns:
            max_result = max(max_result, (reduced_proper_ns[-1]/i, reduced_proper_ns[-1]))
    return max_result
In [7]:
solve(10)
Out[7]:
(0.4, 2)
In [8]:
solve(int(1e6))
Out[8]:
(0.42857128571385716, 428570)