login
Mrs. Perkins's quilt: smallest coprime dissection of n X n square.
(Formerly M3267)
11

%I M3267 #59 Oct 06 2017 22:07:09

%S 1,4,6,7,8,9,9,10,10,11,11,11,11,12,12,12,12,13,13,13,13,13,13,14,14,

%T 14,14,14,14,15,15,15,15,15,15,15,15,15,15,16,15,16,16,16,16,16,16,16,

%U 16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17

%N Mrs. Perkins's quilt: smallest coprime dissection of n X n square.

%C The problem is to dissect an n X n square into smaller integer squares, the GCD of whose sides is 1, using the smallest number of squares. The GCD condition excludes dissecting a 6 X 6 into four 3 X 3 squares.

%C The name "Mrs Perkins's Quilt" comes from a problem in one of Dudeney's books, wherein he gives the answer for n = 13. I gave the answers for low n and an upper bound of order n^(1/3) for general n, which Trustrum improved to order log(n). There's an obvious logarithmic lower bound. - _J. H. Conway_, Oct 11 2003

%C All entries shown are known to be correct - see Wynn, 2013. - _N. J. A. Sloane_, Nov 29 2013

%D H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, C3.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Ed Wynn, <a href="/A005670/b005670.txt">Table of n, a(n) for n = 1..120</a>

%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 A. J. W. Duijvestijn, <a href="http://www.squaring.net/downloads/TableI">Table I</a>

%H A. J. W. Duijvestijn, <a href="http://www.squaring.net/downloads/TableII">Table II</a>

%H R. K. Guy, <a href="/A005667/a005667.pdf">Letter to N. J. A. Sloane, 1987</a>

%H Ed Pegg, Jr., <a href="http://demonstrations.wolfram.com/MrsPerkinssQuilts/">Mrs Perkins's Quilts</a> (best known values to 40000)

%H G. B. Trustrum, <a href="http://dx.doi.org/10.1017/S0305004100038573">Mrs Perkins's quilt</a>, Proc. Cambridge Philos. Soc., 61 1965 7-11.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MrsPerkinssQuilt.html">Mrs. Perkins's Quilt</a>

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

%H Ed Wynn, <a href="http://dx.doi.org/10.1016/j.disc.2014.06.022">Exhaustive generation of 'Mrs. Perkins's quilt' square dissections for low orders</a>, Discrete Math. 334 (2014), 38--47. MR3240464

%e Illustrating a(7) = 9: a dissection of a 7 X 7 square into 9 pieces, courtesy of _Ed Pegg Jr_:

%e .___.___.___.___.___.___.___

%e |...........|.......|.......|

%e |...........|.......|.......|

%e |...........|.......|.......|

%e |...........|___.___|___.___|

%e |...........|...|...|.......|

%e |___.___.___|___|___|.......|

%e |...............|...|.......|

%e |...............|___|___.___|

%e |...............|...........|

%e |...............|...........|

%e |...............|...........|

%e |...............|...........|

%e |...............|...........|

%e |___.___.___.___|___.___.___|

%e The Duijvestijn code for this is {{3,2,2},{1,1,2},{4,1},{3}}

%e Solutions for n = 1..10: 1 {{1}}

%e 2 {{1, 1}, {1, 1}}

%e 3 {{2, 1}, {1}, {1, 1, 1}}

%e 4 {{2, 2}, {2, 1, 1}, {1, 1}}

%e 5 {{3, 2}, {1, 1}, {2, 1, 2}, {1}}

%e 6 {{3, 3}, {3, 2, 1}, {1}, {1, 1, 1}}

%e 7 {{4, 3}, {1, 2}, {3, 1, 1}, {2, 2}}

%e 8 {{4, 4}, {4, 2, 2}, {2, 1, 1}, {1, 1}}

%e 9 {{5, 4}, {1, 1, 2}, {4, 2, 1}, {3}, {2}}

%e 10 {{5, 5}, {5, 3, 2}, {1, 1}, {2, 1, 2}, {1}}

%Y Cf. A005842, A089046, A089047.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

%E b-file from Wynn 2013, added by _N. J. A. Sloane_, Nov 29 2013