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.
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 $.
from math import gcd, floor, ceil
3/ 7
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)))
get_bounds(10)
get_bounds(int(1e6))
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
solve(10)
solve(int(1e6))