|
%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
|
