Tiling a minimal perimeter region with $n$ unit squares Suppose I have $n$ identical unit squares and I want to use them all to tile a region with minimal perimeter $p(n)$. For instance I guess $p(n^2)=4n$, by arranging them im a $n\times n$ square.
Is there an explicit formula for $p(n)$? Or sharp bounds? How do one prove equalities or bounds for this type of quantities?
I would be happy also with a recursive formula for $p(n)$, like $p(n\cdot m) = f(p(m),p(n))$, but the factorization is not unique and I don't see how to get it easily.
My intuition is that given a certain number $n$, the minimal perimeter region is a rectangle with sides of integer lengths $l$ and $m$, where $l\cdot m=n$ and $(l,m)$ is the pair of integer numbers "closest" (in some sense) to $(\sqrt{n},\sqrt{n})$, that's where number theory could play a role.
I have no clue where to start proving something along these lines, so any hint, comment or reference is welcome!
 A: For every x in the range $n^2 \le x < (n+1)^2$ you have $4n \le p(x) \le 4n+4$, so $p(x) = \sqrt{x} + \operatorname{O}(1)$. If you want a closed formula I would try with (putting $t=n^2-x$)
$$ p(n^2+t) = \begin{cases}
4n \quad&\text{if }t=0\\4n+2 &\text{if }0 < t \le n\\ 4n+4 &\text{if }n < t \le 2n\end{cases}$$
which is the perimeter you obtain if you go from the  square $n\times n$ to the square $(n+1)\times(n+1)$ tile by tile.
EDIT (Proof sketch)
We can assume that the shape with least perimeter is connected (if the shape has two pieces, connecting them by a suitable edge gives a shape with strictly less perimeter than the original).
Now given $x = n^2+t$ with $0\le t \le 2n$ fix a shape that gives the least perimeter $p(x)$. Pick a rectangle with minimal dimensions $a\times b$ containing the shape. The perimeter is at least $2a+2b$, (as it goes all the way from left to right and from top to bottom and back by the other side).
On the other hand $ab \ge x$ because there are at least $x$ tiles inside the rectangle so
$$ p(x) \ge 2a + 2b \ge 2a + 2x/a $$
the right hand side has a single minimum at $a = \sqrt{x}$ but $a$ is an integer so we have
$$ p(x) \ge 2n + 2x/n = \frac{ 4n^2 + 2t}{n} $$
(it is easy to see that $a=n+1$ gives a larger value).  If $t = 0$ this gives $p(x) \ge  4n$, if $t \le n$  we have $p(x) > 4n$ but as $p(x)$ is even we have $p(x) \ge 4n+2$ and if $t > n$ we have  $p(x) > 4n+2$ so again $p(x) \ge 4n+4$. As we have examples obtaining this bounds we are finished.
