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

假定有分数n/d, n和d都是正整数。若n<d且GCD(n,d)=1, 那么就称它为最简真分数。

分母d不大于8的最简真分数按大小升序排列如下:

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

可见, 1/3和1/2之间有三个分数。

请你按大小升序列出分母d不大于1,2000时的最简真分数, 问其中1/3和1/2之间有多少个分数。

"""


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




import math
def solution(limit: int = 12000) -> int:

    rpfSet = set()
    for p in range(1, limit):
        for q in range(2*p+1, min(limit+1, 3*p)):
            g = math.gcd(p, q)
            rpfSet.add((p//g, q//g))

    return len(rpfSet)


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

    print(solution())
    # 7295372