Csdrhrt

I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The following is work towards a solution I have made.

Let's denote a rectangle with width and height $x$ and $y$ respectively $(x,y)$. To form new rectangles you can consider cutting a kind of stairway down the diagonal (as is shown in in the problem description) with d steps. But to form a new rectangle the following must hold: $d|x$ and either $(d-1)|y$ or $(d+1)|y$. The new rectangle then becomes either (${x(d-1)}over{d}$, ${yd}over{d-1}$) or (${x(d+1)}over{d}$, ${yd}over{d+1}$). Obviously the new rectangle's area is the same as the old rectangle's.

That was enough to confirm that $G(10)=55$ and $G(1000)=971745$ by looping through all relevant d and adding all new rectangles to a set being careful to count $(x,y)$ and $(y,x)$ only once.

The main issue with this method is that it's possible to make a new rectangle in two different ways. For example, $(9,8)$ can transform into both $(6,12)$ and $(12,6)$ with $d=3$ and either $d-1$ or $d+1$ dividing $y$. Or another example of $(4,4)$ transforms into both $(2,8)$ and $(8,2)$ with $d=2$ and $d=1$ respectively.

I was then lucky enough to read this blog post. It removes the need to check for duplicates by searching for one of the sides instead.

def F(w, h):

    if w&1 and h&1: return 0

    if w<h: w,h = h,w



    r = 0

    x = 1

    while x**2 <= w*h:

        if (w*h)%x!=0 or x==h:

            x += 1

            continue



        if w%(w-x)==0 or x%(x-h)==0:

            r += 1



        x += 1



    return r



def G(N):

    s = 0

    for w in range(1, N+1):

        for h in range(1, w+1):

            s += F(w,h)



    return s

G(10¹²) would require far too long to solve regardless of how fast F is though. I think it's necessary to either use some kind of sieving algorithm where we loop through all x < 10¹² counting how many (w,h) satisfy h $le$ w $le$ 10¹², x|(wh), x $ne$ h and (w-x)|w or (x-h)|x $implies$ (x-h)|h.

I think an O(n^2/3) algorithm must be possible... but I'm stuck here!

Edit: On the suggestion I've checked for a few basic patterns in G(n). If gcd(a,b)=1, G(ab) $ne$ G(a)G(b) in general (for instance G(2)=1, G(5)=8, G(10)=55). In fact it seems G(ab) $ge$ G(a)G(b).

Looking at G(2ⁿ) I have noticed it grows exponentially but very little else. It doesn't show any obvious patterns modulo small primes. The same goes for G(5ⁿ). In general, G(kⁿ) grows about as fast as k²ⁿ.

Edit2: Here's the table of F(w,h) for $w$, $h$ $le$ 10:

    1 2 3 4 5 6 7 8 9 10



 1  0 0 0 1 0 1 0 1 0 1

 2  0 1 1 1 1 2 1 2 2 2

 3  0 1 0 1 0 1 0 2 0 2

 4  1 1 1 1 1 2 1 1 3 2

 5  0 1 0 1 0 1 0 1 0 0

 6  1 2 1 2 1 2 1 2 1 3

 7  0 1 0 1 0 1 0 1 0 1

 8  1 2 2 1 1 2 1 1 2 2

 9  0 2 0 3 0 1 0 2 0 2

10  1 2 2 2 0 3 1 2 2 1

It's symmetrical about the diagonal since F(w,h)=F(h,w).

By analyzing $sum_{i=1}^{N} F(i,N)$ and comparing it with $sum_{i|N} lfloor frac{N}{i+1} rfloor + lfloor frac{N}{i-1} rfloor$, I observe that $sum_{i=1}^{N}F(i,N)$ may be equal to $$sum_{i|N}( lfloor frac{N}{i+1} rfloor + lfloor frac{N}{i-1} rfloor+1) - sum_{(ij)|N}1 - sum_{i(i+1)|N}1.$$ Numerical results of small cases agree with the formula, and formal proof is appreciated.