Side length of the smallest square that can be dissected into $n$ squares with integer sides Let $s_n$ be the shortest possible side length of a square constructed from exactly $n$ squares of positive integer side lengths. If no such square exists, let $s_n = 0$.
The first few values are as follows:
 n | s(n)
---+------
 1 |  1
 2 |  0
 3 |  0
 4 |  2
 5 |  0
 6 |  3
 7 |  4
 8 |  4
 9 |  3
10 |  4
11 |  5
12 |  6
13 |  4
14 |  5

If we search this Integer Sequence in an Online Encyclopedia, something very remarkable happens: there is exactly one search hit. That sequence is A300001, or in English, "Side length of the smallest equilateral triangle that can be dissected into n equilateral triangles with integer sides, or 0 if no such triangle exists."

Do my square sequence's values agree with the triangle sequence's values?
If so, why? If not, when do they first disagree?

At first I thought, maybe there's some manner of bijection between my square dissections and the triangular dissections: if you halve each subsquare along its diagonals, numerically the result should fit in the entire square halved along its own diagonal. But fitting them together requires some nonobvious geometrical fiddling, and I'm not at all confident this subobject-size-preserving bijection is well defined over all dissections. Is it?
 A: First, think about the area of the small squares and the large square.  If you start with $n$ unit squares you have a total area of $n$.  You can replace some of them with $2 \times 2$ squares and add $3$ units each time and replace some others with $3 \times 3$ squares and add $8$ units each time.  You need to do enough of this to increase $n$ to a perfect square.  
The largest number you cannot make out of a sum of $3$'s and $8$'s is $13$ from the coin problem.  This explains why $s(12)=6$.  To make a square of side $5$ out of $12$ squares you would have to add $13$ units of area, but you can't.  Once $n$ is at least $35$ we can always make $(\lceil \sqrt n \rceil+1)^2$ by adding $3$s and $8$s.  We might be able to make $(\lceil \sqrt n \rceil)^2$.  
The reason that squares and triangles work the same is that the area scales as the square of the side for both, so the argument above works the same.  Now we have to argue that once $n$ is large enough you have enough freedom from the remaining size $1$ squares or triangles that we can always form the large figure we want to.  Referring to the example of $12$, we can make the area $36$ by using $3\ 3\times 3$ squares and $9\ 1 \times 1$ squares.  Assembling them into a $6 \times 6$ square is easy.  
For a given $n\ge 35$, let $k=\lceil \sqrt n \rceil.$ The most we have to increase the area is $13+2k+1$, because if $k^2-n \gt 13$ we can make $k^2$.  I don't have a concise argument that we can fit the larger squares, but there are so few of them it is not hard.
