A221844 Number of prime dissections of an n X n square into integer-sided squares up to symmetry.

1, 1, 2, 11, 76, 1490, 56977, 4495010, 669203525

Offset: 1

Author

Geoffrey H. Morley, Jan 26 2013

Keywords

• nonn
• more

Comments

A dissection into squares was called prime by J. H. Conway in 1964 if the GCD of the sides of the squares is 1.

Examples

			For n = 4 there are a(4) = 11 dissections:
+-+-+-+-+ +---+-+-+ +-+---+-+ +-+-+-+-+ +---+---+ +---+-+-+
| | | | | |   | | | | |   | | | | | | | |   |   | |   | | |
+-+-+-+-+ |   +-+-+ +-+   +-+ +-+-+-+-+ |   |   | |   +-+-+
| | | | | |   | | | | |   | | | |   | | |   |   | |   |   |
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+   +-+ +-+-+-+-+ +-+-+   |
| | | | | | | | | | | | | | | | |   | | | | | | | | | |   |
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
+-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+
...
+---+-+-+ +-+---+-+ +---+---+ +---+---+ +-----+-+
|   | | | | |   | | |   |   | |   |   | |     | |
|   +-+-+ +-+   +-+ |   |   | |   |   | |     +-+
|   | | | | |   | | |   |   | |   |   | |     | |
+-+-+-+-+ +-+---+-+ +---+-+-+ +-+-+-+-+ |     +-+
| | |   | | |   | | |   | | | | |   | | |     | |
+-+-+   | +-+   +-+ |   +-+-+ +-+   +-+ +-+-+-+-+
| | |   | | |   | | |   | | | | |   | | | | | | |
+-+-+---+ +-+---+-+ +---+-+-+ +-+---+-+ +-+-+-+-+
...
For n = 5 there are a(5) = 76 dissections, each of which comprises one of A221843(5) = 10 sets of subsquares:
.
            Subsquares             Prime dissections
  4 X 4   3 X 3   2 X 2   1 X 1    (up to symmetry)
  -----   -----   -----   -----    ----------------
    -       -       -       25             1
    -       -       1       21             3
    -       -       2       17            13
    -       -       3       13            20
    -       -       4        9            14
    -       1       -       16             3
    -       1       1       12             6
    -       1       2        8            10
    -       1       3        4             5
    1       -       -        9             1
                                          --
                                          76
		

Links

• J. H. Conway, Mrs. Perkins's quilt, Proc. Camb. Phil. Soc., 60 (1964), 363-368.
• Ed Wynn, Exhaustive generation of Mrs Perkins's quilt square dissections for low orders, 2013, arXiv:1308.5420

Crossrefs

Cf. A221843, A221845.

Extensions

More terms from Wynn, 2013. - N. J. A. Sloane, Nov 29 2013