# Project Euler Problem 338

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(1012) 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 < 1012 counting how many (w,h) satisfy h $\le$ w $\le$ 1012, x|(wh), x $\ne$ h and (w-x)|w or (x-h)|x $\implies$ (x-h)|h.

I think an O(n2/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(2n) 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(5n). In general, G(kn) grows about as fast as k2n.

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).

-
I see no reason to think it is possible to count by brute force. My first try would be to see if whenever $\gcd(a,b)=1,$ does it follow that $G(ab) = G(a) G(b).$ I have no idea, by the way. Then I would check low powers and see if I could find a pattern in $G(2^k)$ and then $G(5^m).$ – Will Jagy Sep 19 '11 at 22:09
Alright, I don't think I want to write any programs for this. Could you please post a little table of all the separate F(w,h) with 1 <= h <= w <= 10? Evidently the interesting relationships occur there, not in the cumulative function G. – Will Jagy Sep 20 '11 at 3:26
Sorry if it's not much related to the question. But I'm curious if we could prove that dividing into two staircases is the only way of forming another rectangle. How can we do this? – Jineon Baek Sep 20 '11 at 12:56
I voted to close because I do think that it is a very bad idea to have a collection of project Euler solutions here. – Phira Oct 4 '11 at 10:39