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

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, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

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.

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

All entries shown are known to be correct - see Wynn, 2013. - N. J. A. Sloane, Nov 29 2013

Examples

			Illustrating a(7) = 9: a dissection of a 7 X 7 square into 9 pieces, courtesy of _Ed Pegg Jr_:
.___.___.___.___.___.___.___
|...........|.......|.......|
|...........|.......|.......|
|...........|.......|.......|
|...........|___.___|___.___|
|...........|...|...|.......|
|___.___.___|___|___|.......|
|...............|...|.......|
|...............|___|___.___|
|...............|...........|
|...............|...........|
|...............|...........|
|...............|...........|
|...............|...........|
|___.___.___.___|___.___.___|
The Duijvestijn code for this is {{3,2,2},{1,1,2},{4,1},{3}}
Solutions for n = 1..10: 1 {{1}}
2 {{1, 1}, {1, 1}}
3 {{2, 1}, {1}, {1, 1, 1}}
4 {{2, 2}, {2, 1, 1}, {1, 1}}
5 {{3, 2}, {1, 1}, {2, 1, 2}, {1}}
6 {{3, 3}, {3, 2, 1}, {1}, {1, 1, 1}}
7 {{4, 3}, {1, 2}, {3, 1, 1}, {2, 2}}
8 {{4, 4}, {4, 2, 2}, {2, 1, 1}, {1, 1}}
9 {{5, 4}, {1, 1, 2}, {4, 2, 1}, {3}, {2}}
10 {{5, 5}, {5, 3, 2}, {1, 1}, {2, 1, 2}, {1}}
		

References

• H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, C3.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Ed Wynn, Table of n, a(n) for n = 1..120
• J. H. Conway, Mrs. Perkins's quilt, Proc. Camb. Phil. Soc., 60 (1964), 363-368.
• A. J. W. Duijvestijn, Table I
• A. J. W. Duijvestijn, Table II
• R. K. Guy, Letter to N. J. A. Sloane, 1987
• Ed Pegg, Jr., Mrs Perkins's Quilts (best known values to 40000)
• G. B. Trustrum, Mrs Perkins's quilt, Proc. Cambridge Philos. Soc., 61 1965 7-11.
• Eric Weisstein's World of Mathematics, Mrs. Perkins's Quilt
• Ed Wynn, Exhaustive generation of 'Mrs Perkins's quilt' square dissections for low orders, arXiv:1308.5420 [math.CO], 2013-2014.
• Ed Wynn, Exhaustive generation of 'Mrs. Perkins's quilt' square dissections for low orders, Discrete Math. 334 (2014), 38--47. MR3240464

Crossrefs

Cf. A005842, A089046, A089047.

Extensions

b-file from Wynn 2013, added by N. J. A. Sloane, Nov 29 2013