How many squares in a rectangle?

Question

I almost wish I'd never thought of this problem... I was tearing my hair out over it all night.

Suppose we have a rectangle with side lengths $a$ and $b$, $a,b \in \mathbb Z$, $GCD(a,b)=1$, and $b \gt a$. I want to pack squares in this rectangle in such a way that, at each step, I pack a squares that is large as possible at that step, and that touches the square I packed at the last step. A square packing of this type might end up looking something like this:

My question is this: can I find a formula for the number of squares needed to pack a rectangle in terms of its side lengths $a$ and $b$?

Here is what I tried:

First I let $f(a,b)$ denote the function whose output is the number of squares required. First, I noted a few properties of $f(a,b)$: $$f(a,a)=1$$ $$f(ka,kb)=f(a,b)$$ $$f(a,a+1)=a+1$$ $$f(a,b)=\Big\lfloor \frac{a}{b} \Big\rfloor + f(b, a\mod b)$$ $$r \lt a \implies f(a,qa+r)=q+f(r,a)$$ Next I tried this: I decided to let $b=q_1a+r_1$ where $r_1 \lt a$. Then I would have $$f(a, q_1a+r_1)=q_1+f(r_1, a)$$ Then I decided to let $a=q_2r_1+r_2$, so that we would then have $$f(a, q_1a+r_1)=q_1+f(r_1, q_2r_1+r_2)$$ $$f(a, q_1a+r_1)=q_1+q_2+f(r_2, r_1)$$ and so on. I keep continuing this process until I hit some $n$ for which $r_n=0$, and I will have $$f(a, q_1a+r_1)=\sum_{i=1}^n q_i$$ ...and then I got stuck. How can I find each of the $q_i$s? Somebody, please help! The solution need not be closed-form, it just needs to be... something. I just have no idea where to go with this.

Thanks for any and all help!

Answer 1

$$f(a,b) = \begin{cases}1 & a= b\\b/a & (\gcd(a,b) = a) ∧ (a\neq b)\\ a/b & (\gcd(a,b) = b) ∧ (a\neq b) \\ f(b,a) & b>a\\ \frac{(a-(a \mod b))}{b} + f(b,(a\mod b)) &a>b\end{cases}$$

$$\gcd(x,y) =\begin{cases}x&x=y\\y & (x = 0)∧(x\neq y)\\x & (y=0)∧(x\neq y)\\\gcd(y,(x\mod y))&x>y\\\gcd((y\mod x),x)&y> x\end{cases}$$

(∧: AND logical operator)

$f(a,b)$ is the function that solves your question, using $\gcd(x,y)$, Euclid's GCD function.

Here's also the code written in Swift that does the same thing:

import Foundation
func ourFunction (_ a: Int, _ b: Int) -> Int{
    if gcd(a,b) == a{
        return b/a
    }else if gcd(a,b) == b{
        return a/b
    }
    if b>a{
        // Force a to be bigger than b
        return ourFunction(b,a)
    }
    return (a-(a%b)) / b /*big squares*/ + ourFunction(b,a%b)
}

func gcd(_ x:Int, _ y:Int) -> Int{
    if x == 0 || x == y{
        return y
    }
    if y == 0{
        return x
    }
    if x > y{
        return gcd(y,x%y)
    }else{
        return gcd(y%x,x)
    }
}
print(ourFunction(8,3))

It can be run here, just change the $8$ and $3$ to the numbers you want to put into the function.

Answer 2

The answer by @MCCCS is great, but I provide an alternative answer with intent of being (slightly) more concise.

The problem can be solved recursively by embedding as many equally-sized maximal squares as possible within the rectangle and increasing a counter by the number of squares embedded. You'll end up with a smaller rectangle, for which you can embed another (horizontal or vertical) stack of equally-sized maximal squares as possible. Rinse repeat!

This recursive process can be described by the following recursive function:

$$f(a, b) = \begin{cases} 0 &\mbox{if } a =0 \lor b=0 \\ f(a, b-a\cdot\left \lfloor \frac{b}{a} \right \rfloor) + \left \lfloor \frac{b}{a} \right \rfloor & \mbox{if } a<b \\ f(a-b \cdot \left \lfloor \frac{a}{b} \right \rfloor, b) + \left \lfloor \frac{a}{b} \right \rfloor & \text{otherwise} \end{cases}$$

whose domain is $\{\forall(a,b)\in \mathbb{R}^2:\gcd(a,b)=1\}$.

Here is a C-program implementing the function described above:

#include <stdio.h>

int f(int w, int h) {
    return  w == 0 || h == 0 ? 0 :
            w < h ? f(w, h-w*(h/w)) + h/w :
            f(w-h*(w/h), h) + w/h;
}

int main(int argc, char** argv) {
    int i = 3, j = 7;
    printf("f(%i, %i)=%i\n", i, j, f(i, j));
    return 0;
}