|
|
A005670
|
|
Mrs. Perkins's quilt: smallest coprime dissection of n X n square.
(Formerly M3267)
|
|
10
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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
|
|
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
|
|
|
EXAMPLE
|
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}}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|