PyPE solution to PE problem 73

    ProjectEuler.net problem 73
    ===========================

    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 there are 3 fractions between 1/3 and 1/2.

    How many fractions lie between 1/3 and 1/2 in the sorted set of reduced
    proper fractions for d 12,000?

    Note: The upper limit has been changed recently.

    Solution
    --------

    The solution provided herein is borrowed from Polytope (PE forums). Note
    that the original solution was similar to the one employed for problem 71,
    though it took a significant amount of time to execute.

    Polytope's solution defines two functions, g(n) denoting the number of pairs
    of positive integers x,y such that y <= n and 1/3 < x/y < 1/2, and f(n)
    denoting a subset of the number of pairs with the additional constraint
    that x and y are relatively prime.

    Not proven here is that

        g(n) = sum (k=1 to n) f(n/k),

    to which you can apply the Mobius inversion to get

        f(n) = sum (k=1 to n) mu(k) * g(n/k),

    where mu(k) is the Mobius function. The solution to our problem is f(n)
    with n equal to our maximum value for d, in this case 12,000.

    An additional useful formula obtained by Polytop is that

        g(n) = round( (n-2)**2 / 12 )

    is the total number of x,y pairs satisfying the above criteria.

    Answer
    ------

    7295372