[Math Puzzle] 21

Even numbers, cut one large square from the whole, and then split the remaining part into squares. The thinner the remaining part, the more squares can be cut. This will support any number of squares of an even number excluding 2. For odd numbers, the large square that you initially cut, split it into 4 squares and do the same thing. This will work for any odd number excluding 3 and 5.

http://oeis.org/A074764

Turning one square into 4 is easy: Just split it down and across the middle. So, given any size square we can make it into 3 more. This process is repeatable as well. Now, we need to figure out how to make 0, 1 and 2 (mod 3) squares.

First, 0mod3: Think Tic-Tac-Toe. Making 9 squares initially with 4 cuts means we can make 12, 15, 18, etc.

Next, 1: Again, we go back to the simplest split, down and across the middle. From 4 initial squares we can make 7, 10, 13...

For 2mod3: Make a 4x4 grid and take a 3x3 large square in one corner. You're left with 7 1x1 squares, meaning 8 total. From 8, we can do 11, 14, 17...

Meh, you can add 2 squares to any 4 square lattice by changing it into 6 squares, a 6 square by changing it into an 8 square etc. You get 6 squares by making a 9 square lattice and then removing the cross in a 4 square, continue adding 2 squares in the same way by extending the edges while keeping one large square. So thus you can easily add 2 squares to anything originally containing a 4 square lattice, so you just need to find an even and an odd containing a 4 square lattice. We already got the trivial 4 square lattice, and if we take the 4 square and make a 4 square in one of the corners we get 7 squares. Done.

Let N = number of squares required, and the initial square having a length of 1.
The length of the first square to cut can be calculated by:
1-2/N if N is even
1-2/(N-3) if N is odd (which is then to be divided into 4 equal pieces)

Then just cut along the the remaining L shape for squares until done.

I just did it empirically.. the same way as stenole, except a different way of getting to 12, since I came up with the L shaped one last. Cutting a square into 4 pieces adds 3 squares, cutting a square into 9 pieces adds 8 squares, and cutting a square into one big one and 5 little ones adds 5 squares. You get 10 by 1+3+3+3, you get 11 by 1+5+5, and you get 12 by 1+3+8. Add multiples of 3 to any number above that and you're set.

This doesn't count for the last possible number, which is 8- for 8 you need another "corner-border representation" of 1 big square and a L of 7 little squares, but it answered the question

I agree, Chairman's approach is the simplest/best