A221844 - OEIS

%I #31 Sep 06 2021 04:29:35

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

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

%C A dissection into squares was called prime by _J. H. Conway_ in 1964 if the GCD of the sides of the squares is 1.

%H J. H. Conway, <a href="http://dx.doi.org/10.1017/S0305004100037877">Mrs. Perkins's quilt</a>, Proc. Camb. Phil. Soc., 60 (1964), 363-368.

%H Ed Wynn, <a href="http://arxiv.org/abs/1308.5420">Exhaustive generation of Mrs Perkins's quilt square dissections for low orders</a>, 2013, arXiv:1308.5420

%e For n = 4 there are a(4) = 11 dissections:

%e +-+-+-+-+ +---+-+-+ +-+---+-+ +-+-+-+-+ +---+---+ +---+-+-+

%e | | | | | |   | | | | |   | | | | | | | |   |   | |   | | |

%e +-+-+-+-+ |   +-+-+ +-+   +-+ +-+-+-+-+ |   |   | |   +-+-+

%e | | | | | |   | | | | |   | | | |   | | |   |   | |   |   |

%e +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+   +-+ +-+-+-+-+ +-+-+   |

%e | | | | | | | | | | | | | | | | |   | | | | | | | | | |   |

%e +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+

%e | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

%e +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+-+-+

%e ...

%e +---+-+-+ +-+---+-+ +---+---+ +---+---+ +-----+-+

%e |   | | | | |   | | |   |   | |   |   | |     | |

%e |   +-+-+ +-+   +-+ |   |   | |   |   | |     +-+

%e |   | | | | |   | | |   |   | |   |   | |     | |

%e +-+-+-+-+ +-+---+-+ +---+-+-+ +-+-+-+-+ |     +-+

%e | | |   | | |   | | |   | | | | |   | | |     | |

%e +-+-+   | +-+   +-+ |   +-+-+ +-+   +-+ +-+-+-+-+

%e | | |   | | |   | | |   | | | | |   | | | | | | |

%e +-+-+---+ +-+---+-+ +---+-+-+ +-+---+-+ +-+-+-+-+

%e ...

%e For n = 5 there are a(5) = 76 dissections, each of which comprises one of A221843(5) = 10 sets of subsquares:

%e .

%e             Subsquares             Prime dissections

%e   4 X 4   3 X 3   2 X 2   1 X 1    (up to symmetry)

%e   -----   -----   -----   -----    ----------------

%e     -       -       -       25             1

%e     -       -       1       21             3

%e     -       -       2       17            13

%e     -       -       3       13            20

%e     -       -       4        9            14

%e     -       1       -       16             3

%e     -       1       1       12             6

%e     -       1       2        8            10

%e     -       1       3        4             5

%e     1       -       -        9             1

%e                                           --

%e                                           76

%Y Cf. A221843, A221845.

%K nonn,more

%O 1,3

%A _Geoffrey H. Morley_, Jan 26 2013

%E More terms from Wynn, 2013. - _N. J. A. Sloane_, Nov 29 2013