For what natural $n$ does there exist a square composed of $n$ squares?

I recently stumbled upon a cute puzzle involving squares:

For what natural $$n$$ does there exist a square composed of $$n$$ squares?

For example, $$1,4,$$ and $$6$$ are valid:

But $$2$$ and $$3$$ are not valid.

• Related. Aug 7 '19 at 18:24
• :P the problem here is much much simpler, though that does look interesting as well! Aug 7 '19 at 18:27
• Any even number $2n$ is valid, as it can be expressed with $2n-1$ squares of size $1$ and $1$ square of size $(n-1)^2$. Aug 7 '19 at 18:37
• Interestingly, this already had an answer for $(n\ge 6)$ and $(n=5)$ here on MSE, but they were not easy to find when I searched for similar questions like this one. Jan 12 '20 at 17:56

Note first that you can always add three squares to a configuration by splitting one sub-square into four.

Then take a $$3\times 3$$ square out of the corner of a square of side $$4$$ to find a configuration with $$8$$ squares.

This gives $$1+3n; 6+3n; 8+3n$$ as possibles, leaving just $$2,3,5$$ as impossible.

See also the comment on cute squares in this link: https://en.wikipedia.org/wiki/Squaring_the_square which says it can be done with squares of no more than two sizes for all positive integers other than 2,3,5.

• +1 this was my solution Aug 7 '19 at 18:43
• @SimplyBeautifulArt: When you already have a solution, you should include it with your question so that people don't waste time duplicating your work.
– Blue
Aug 7 '19 at 18:47
• @Blue Meh, this question is just for some puzzling fun, not really work at all. The intention was, hopefully, that this answerer and everyone else who tried enjoyed trying the problem on their own. Besides, I've even learned some interesting things from this answer as well. Aug 7 '19 at 18:56
• @SimplyBeautifulArt: That's not really the point of Math.SE. The least you could do is state explicitly that you already have an answer so that people don't think you're looking for help (which is the point of Math.SE). Note that Puzzling.SE exists specifically for "puzzling fun". Even Math.SE's puzzle tag description reads "If the answer is known to you please do not use this tag to 'riddle' other users, but rather to ask about the correctness of a possible solution or ways to extend and improve an existing solution." So, it's not just me. ;)
– Blue
Aug 7 '19 at 19:06
• >:P Okay then thanks for pointing it out then @Blue Aug 7 '19 at 19:10

There is no way to add one square to an arrangement and still get only squares. You can add 2 squares to any arrangement after the first 2 and still have all squares (for example, your move from 4 to 6 squares). You can also always add 3 squares and still get only squares (for example, from 1 to 4). You do this by breaking any given square into 4 squares. You can also add 5 squares by starting with a 3x3 that is 1 square and breaking up the first row and the first column into squares. But this can also be achieved by starting with a 4x4 and adding 2 squares. There is no other way to add squares to any arrangement. Therefore, $$n = 1 + 2a + 3b,$$ where $$b \geq 0$$, $$a \geq 0$$, and for $$b = 0$$ you must have $$a=0$$, since you cannot add 2 on the first step.

• How are you "adding 2 squares"? For example, how do you go from 6 to 8? Aug 7 '19 at 18:40
• @SimplyBeautifulArt Add two squares next to the ones labelled $3$ and $5$ of the same area. Then increase the area of the square labelled $6$. Aug 7 '19 at 18:44
• Then how do you go from 7 to 9? Aug 7 '19 at 18:45
• Say you had your square with 4 squares above. Split the lower right into 4 to have 7 total now. Add a square above the square labeled 2 and another to the left of the square labeled 3 and increase the size of 1. Aug 9 '19 at 17:38