cp's OEIS Frontend

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

%I A005670 M3267 #60 Feb 16 2025 08:32:29
%S A005670 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 A005670 14,14,14,14,15,15,15,15,15,15,15,15,15,15,16,15,16,16,16,16,16,16,16,
%U A005670 16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17
%N A005670 Mrs. Perkins's quilt: smallest coprime dissection of n X n square.
%C A005670 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 A005670 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 A005670 All entries shown are known to be correct - see Wynn, 2013. - _N. J. A. Sloane_, Nov 29 2013
%D A005670 H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, C3.
%D A005670 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005670 Ed Wynn, <a href="/A005670/b005670.txt">Table of n, a(n) for n = 1..120</a>
%H A005670 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 A005670 A. J. W. Duijvestijn, <a href="http://www.squaring.net/downloads/TableI">Table I</a>
%H A005670 A. J. W. Duijvestijn, <a href="http://www.squaring.net/downloads/TableII">Table II</a>
%H A005670 R. K. Guy, <a href="/A005667/a005667.pdf">Letter to N. J. A. Sloane, 1987</a>
%H A005670 Ed Pegg, Jr., <a href="http://demonstrations.wolfram.com/MrsPerkinssQuilts/">Mrs Perkins's Quilts</a> (best known values to 40000)
%H A005670 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 A005670 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MrsPerkinssQuilt.html">Mrs. Perkins's Quilt</a>
%H A005670 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 A005670 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 A005670 Illustrating a(7) = 9: a dissection of a 7 X 7 square into 9 pieces, courtesy of _Ed Pegg Jr_:
%e A005670 .___.___.___.___.___.___.___
%e A005670 |...........|.......|.......|
%e A005670 |...........|.......|.......|
%e A005670 |...........|.......|.......|
%e A005670 |...........|___.___|___.___|
%e A005670 |...........|...|...|.......|
%e A005670 |___.___.___|___|___|.......|
%e A005670 |...............|...|.......|
%e A005670 |...............|___|___.___|
%e A005670 |...............|...........|
%e A005670 |...............|...........|
%e A005670 |...............|...........|
%e A005670 |...............|...........|
%e A005670 |...............|...........|
%e A005670 |___.___.___.___|___.___.___|
%e A005670 The Duijvestijn code for this is {{3,2,2},{1,1,2},{4,1},{3}}
%e A005670 Solutions for n = 1..10: 1 {{1}}
%e A005670 2 {{1, 1}, {1, 1}}
%e A005670 3 {{2, 1}, {1}, {1, 1, 1}}
%e A005670 4 {{2, 2}, {2, 1, 1}, {1, 1}}
%e A005670 5 {{3, 2}, {1, 1}, {2, 1, 2}, {1}}
%e A005670 6 {{3, 3}, {3, 2, 1}, {1}, {1, 1, 1}}
%e A005670 7 {{4, 3}, {1, 2}, {3, 1, 1}, {2, 2}}
%e A005670 8 {{4, 4}, {4, 2, 2}, {2, 1, 1}, {1, 1}}
%e A005670 9 {{5, 4}, {1, 1, 2}, {4, 2, 1}, {3}, {2}}
%e A005670 10 {{5, 5}, {5, 3, 2}, {1, 1}, {2, 1, 2}, {1}}
%Y A005670 Cf. A005842, A089046, A089047.
%K A005670 nonn,nice
%O A005670 1,2
%A A005670 _N. J. A. Sloane_
%E A005670 b-file from Wynn 2013, added by _N. J. A. Sloane_, Nov 29 2013