PyPE solution to PE problem 85

    ProjectEuler.net problem 85
    ===========================

    By counting carefully it can be seen that a rectangular grid measuring
    3 by 2 contains eighteen rectangles.

    Although there exists no rectangular grid that contains exactly two
    million rectangles, find the area of the grid with the nearest solution.

    Solution
    --------

    First, we take a look at the number of sub-rectangles that can be found in
    an m x n rectangular grid:

        Size Subrectangles
        1 x 1 m*n
        2 x 1 (m-1)*n
        3 x 1 (m-2)*n
         ... ...
        1 x 2 m *(n-1)
        2 x 2 (m-1)*(n-1)
        3 x 2 (m-2)*(n-1)
         ... ...
        1 x 3 m *(n-2)
        2 x 3 (m-1)*(n-2)
        3 x 3 (m-2)*(n-2)
         ... ...

    We can see that the total number of sub-rectangles, which is the sum of the
    values in the right-hand column, is obtained from:

        nSR = ( m + (m-1) + (m-2) + ... + 1 ) * ( n + (n-1) + (n-2) + ... + 1 ),

    each term of which can be simplified using the properties of triangular
    numbers to:

        nSR = ( m*(m-1)/2 ) * ( n*(n-1)/2 ) = m*n*(m-1)*(n-1)/4.

    We now have a very efficient method for calculating the number of sub-
    rectangles in an m x n rectangular grid.

    We are looking for the grid-size that results in the number of sub-rectangles
    that is closest to the target value. There will be a closest grid-size just
    /over/ the target value, and another one just /under/; we will keep track of
    the closest of each type found to date through our algorithm (max_less and
    min_over).

    The first attempted approach is a brute-force approach that tries all m
    from 1 to target, and all n from m to target, checking the number of
    sub-rectangles against the limits found so far at each step. This method
    completed in approximately 8.5 seconds.

    A second, better method is implemented below. We note that we are looking
    for the solution

        nSR = m*n*(m-1)*(n-1)/4 = target,

    but if we have specified one of the variables (m, for example), we can
    solve for n using the quadratic formula:

        n = (-1 +- sqrt(1+(16*target)/(n*(n+1))))/2.

    If the target is not reached exactly, then n will be a float with some value
    after the decimal. We need only check two ns, the nearest integers to the
    solution for n. We check each of these ns against the best solutions to date.
    Once the value of n becomes larger than the largest value of m or n found to
    date, we know that no other solutions will be closer to the target value, so
    we can break from the loop. Note that a rectangular grid of m x n is
    equivalent to one of n x m.

    The two closest grid sizes are 35 x 77, with 1999998 subrectangles, and
    3 x 816, with 2000016 subrectangles. From this, the answer is the former
    35 x 77 grid, with an area of 2772.

    Answer
    ------

    2772