Mrs Perkin's Quilt

Here's an old Dudeney puzzle which presents some quite difficult mathematics. The problem is to divide up Mrs Perkin's quilt into the smallest possible number of smaller square quilts. The original is a 13x13 square, but you can only cut along the seams.

Solving this is very difficult to do. possibly you start with a greedy algorithm approach by taking a 12x12 square, but that leaves you with 12+12+1=25 squares which can only be filled by inefficient 1x1 squares giving you 26 in total. Starting out with an 11x11 is better because you can mostly fill the edges with 2x2s, giving 16 squares in total, but these regular approaches don't get you anyway close to the most efficient answer which is laid out below:

Dudeney hedged his bets with the phrase "I believe" in the book, but Amusements in Mathematics was written in 1917 so it was well before the world of computing got their hands on this problem. But he was correct that it was the most efficient solution and that it was as unique as claimed in the book.

However, the question is an interesting one in mathematics. How few squares can an nxn square be dissected into? There is an additional stipulation that most studies into the problem use: all dissections must be prime in that they are not permitted to be dissected using the same pattern as lower order squares. For example 4x4 (and any 2nx2n for that matter) you would be able to to in the same manner as the 2x2 if this rule wasn't in place.

For n=1 the only possible dissection can be itself, but for all larger squares we will prohibit such a dissection. Below are the diagrams for the first 18:

As you can see these solutions usually have three large quarters, but the details in the fourth quarter are highly chaotic. This is a problem without a nice analytical answer and all we can do is apply bounds to how many squares it will take and use computers to brute force the answers for the smaller ones.

As n increases the number of squares needed isn't strictly increasing. The first example of this is that n=40 needs 16 squares, but n=41 only needs 15. Examples of this sort of behaviour gets more common as the numbers increase.

The first bound for the number of squares that was proven was in 1964 by Conway (Conway and Dudeney in the same article! Such a fanboy) to be of the order n^(1/3), but this was improved upon by someone called Trustrum the year after and it remains at the order of ln(n).