Project Euler #85: Find the rectangular grid with closest to 2M rectangles For one place that I interviewed at (for a Python developer position) I worked with one of the devs on two Project Euler problems, one being problem 85. We talked through different approaches and came up with solutions together, but we coded separately. He seemed impressed that we were able to get through two problems. After the interview, he asked me to clean up the code and submit it, which you can see below. He never got back to me after I sent him the code. I'd like to know what's wrong with my code and not make the same mistakes again. 

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.


# problem85.py
# Project Euler
# Nicolas Hahn

# int m, int n -&gt; # of rectangles that can be made from m*n rectangle
def numRectangles(m,n):
    return (m*n*(m+1)*(n+1))//4

# int 'num' -&gt; side length of first square that has &gt;='num' rectangles
def getLargestSquareLength(num):
    rectNum = 0
    length = 0
    while rectNum &lt; num:
        length += 1
        rectNum = numRectangles(length,length)
    return length

# int 'num' -&gt; area of rectangle with closest to 'num' rectangles
def closestTo(num):
    rects = []
    # start from a square, work towards a 1*n rectangle
    length = getLargestSquareLength(num)
    for i in range(1,length+1):
        m = length-i
        n = m+1
        # find closest rectangle to 'num' with width m
        while numRectangles(m,n) &lt; num and m &gt; 0:
            n += 1
        # store both the &gt;num rectangle and &lt;num rectangle with width m
        rects.append((m,n,numRectangles(m,n)))
        rects.append((m,n-1,numRectangles(m,n-1)))
    # get closest number of rectangles, then compute area
    m,n,r = sorted(rects, key=lambda k: abs(k[2]-num))[0]
    return m*n

def main():
    # correct answer = 2772
    print(closestTo(2000000))

if __name__ == "__main__":
    main()
Well, let's ignore the code, because having started coding at that stage is wrong.

Let's look instead at a better starting-point:


Find a closed formula for the number of rectangles in a grid of given size (x, y):

N = \$\sum_{a=1}^x\sum_{b=1}^y(x-a+1)(y-b+a)\$
\$= \sum_{a=0}^{x-1}\sum_{b=0}^{y-1}(x-a)(y-b)\$
\$ = \frac 1 4 * (2x^2 - x*(x-1))(2y^2 - y*(y-1))\$
\$= \frac 1 4 * (x^2+x)(y^2+y)\$
Solve it for given y and N:

\$x^2+x-\frac{4*N}{y^2+y} = 0\$
\$x=\frac{-1 \pm \sqrt{1 + \frac{4*4*N}{y^2+y}}}2\$
\$x=-\frac 1 2 \pm \sqrt{\frac 1 4 + \frac{4*N}{y^2+y}}\$

(Only the positive solution is of interest)
Simply iterate all possible rectangles starting with short side of 1 until our short dimension becomes the long one, and calculate the number of rectangles for a slightly bigger / smaller rectangle than the fractional one we calculated.


The solution will be found in \$\Theta\left(\sqrt[4]N\right)\$.