"""
Problem 71: https://projecteuler.net/problem=71

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


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/24
'''


def solution(d: int = 1000000, target=3/7) -> list:
    '''
    if p/q is the fraction immediately to the left of 3/7,

    min{3/7 - p/q > 0}, we wish max(p) for q
       p < 3q/7

    because p/q < (p+1)/(q+1), so comparatively speaking, 
    the bigger for q, the better
    we search q inversely to reduce operations

    '''
    res_p = 0
    res_q = 0
    diff = target

    for q in range(d, 0, -1):
        p, m = divmod(3*q, 7)
        if m == 0:
            p -= 1

        tmp = target - p/q

        if tmp < diff:
            res_p, res_q, diff = p, q, tmp
            # very few times (just twice for d = 1000000)

    import math
    g = math.gcd(res_p, res_q)
    res_p, res_q = res_p//g, res_q//g
    return res_p, res_q, res_p/res_q


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # (428570, 999997, 0.42857128571385716)

    # 3/7 = 0.42857142857142855