PyPE solution to PE problem 72

    ProjectEuler.net problem 72
    ===========================

    Consider the fraction, n/d, where n and d are positive integers. If nd 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 21 elements in this set.

    How many elements would be contained in the set of reduced proper fractions
    for d 1,000,000?

    Solution
    --------

    The solution provided herein is borrowed from Polytope's (PE forums)
    algorithm for problem 73, with a modified definition of g(n).

    The function g(n) gives the number of distinct x/y fractions for y = 1..N
    and x = 1..(y-1). The function f(n) denotes a subset of the number of x,y
    pairs with the additional constraint that x and y are relatively prime (i.e.
    that they form a reduced fraction).

    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 10**6.

    Answer
    ------

    303963552391