A089047 -id:A089047 - cp's OEIS frontend

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

N. J. A. Sloane

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

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

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).

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

Cf. A005842, A089046, A089047.

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

A217149 Largest possible side length for a perfect squared square of order n; or 0 if no such square exists.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 112, 192, 332, 479, 661, 825, 1179, 1544, 2134, 2710, 3641, 4988, 6391, 8430, 11216, 15039, 20242

Offset: 1

Geoffrey H. Morley, Sep 27 2012

A squared rectangle (which may be a square) is a rectangle dissected into a finite number, two or more, of squares. If no two of these squares have the same size the squared rectangle is perfect. The order of a squared rectangle is the number of constituent squares. By convention the sides of the subsquares are integers with no common factor.

A squared rectangle is simple if it does not contain a smaller squared rectangle. Every perfect square with the largest known side length for each order up to 37 is simple.

S. E. Anderson, Perfect Squared Rectangles and Squared Squares.
Stuart Anderson, 'Special' Perfect Squared Squares", accessed 2014. - _N. J. A. Sloane_, Mar 30 2014
Ed Pegg Jr., Advances in Squared Squares, Wolfram Community Bulletin, Jul 23 2020
Eric Weisstein's World of Mathematics, Perfect Square Dissection

Cf. A006983, A089047, A129947, A181735, A217148, A217156.

a(29) from Stuart E Anderson added by Geoffrey H. Morley, Nov 23 2012
a(30), a(31), a(32) from Lorenz Milla and Stuart E Anderson, added by Stuart E Anderson, Oct 05 2013
For additional terms see the Ed Pegg link, also A006983. - N. J. A. Sloane, Jul 29 2020
a(33) to a(37) from J. B. Williams added by Stuart E Anderson, Oct 27 2020

A014529 Largest convex area that can be tiled with n equilateral triangles whose sides s_k are relatively prime, i.e., gcd(s_1,...,s_n) = 1.

Original entry on oeis.org

1, 2, 3, 7, 11, 20, 36, 71, 146, 260, 495, 860, 1559, 2831, 5114

Offset: 1

N. J. A. Sloane

The terms published to date (n <= 15) are consistent with a tribonacci growth rate. Specifically, floor(A000073(n+2) * 5/6) <= a(n) <= A000073(n+2). - Peter Munn, Sep 27 2017

a(16) is at least 9322. - Peter Munn, Feb 20 2018

			From _Peter Kagey_, Jul 31 2017: (Start)
For n = 6 a convex polygon with area 20 is:
      *-------*
     / \     / \
    /   \   /   \
   /     \ /     \
  *---*---*       \
   \ / \ /         \
    *---*-----------*
The sides are relatively prime because gcd(1, 1, 1, 2, 2, 3) = 1. (End)

Robert T. Wainwright, quoted by Ian Stewart, Math. Recreations, Scientific American, Jul 15 1997, p. 96.

Hugo Pfoertner, Illustrations of configurations for n <= 11
Hugo Pfoertner, Illustration of configuration for n = 12, based on personal communication from _Peter Munn_
Hugo Pfoertner, Illustration of configuration for n = 13, based on data in A289944 from _Peter Munn_
Rainer Rosenthal, Illustration of configuration for n = 14, based on description in A289944 from _Peter Munn_
Rainer Rosenthal, Illustration of configuration for n = 15, based on description in A289944 from _Peter Munn_
Ian Stewart, Die unscheinbare Schwester der goldenen Zahl, Spektrum der Wissenschaft, Dossier 02/2003: Mathematische Unterhaltungen II, 55-57.

Cf. A000073, A089047, A133044, A289944.

Terms a(12)-a(15) from John W. Layman

A290821 Side length of largest equilateral triangle that can be made from n or fewer equilateral triangles with integer sides s_k, subject to gcd(s_1,s_2,...,s_n) = 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 39, 49

Offset: 1

Hugo Pfoertner, Aug 11 2017

No construction from 2, 3 or 5 equilateral triangles exists. The first difference from the Padovan numbers occurs for a(15)=39, where the corresponding term A000931(19)=37. a(16)=A000931(20)=49. a(n) >= A000931(n+3). From the growth behavior of A290697 it is conjectured that a(k) > A000931(k+3) for all k > 20.
a(19) is at least 130. This compares with A000931(23) = 114. It hints of growth behavior similar to sqrt(A014529) or sqrt(A001590). Ceiling(sqrt(A001590(n))) matches a(n) to n=14, then runs 38, 52, 70, 95, 128, ... . - Peter Munn, Mar 10 2018
From Peter Munn, Mar 14 2018 re monotonicity: (Start)
For n >= 6, a(n+1) > a(n).
Sketch of proof (inductive step) expressed in terms of tiling:
Given a triangle of side a(n) tiled with n equilateral triangular tiles. Let X, Y and Z be the tiles incident on its vertices, with X being not smaller than Y or Z.
Case 1: Y and Z have no vertices coincident. Remove Y and Z, thereby reducing the tiled area to a pentagon that has edges A and C that were previously internal to the area, and an edge B between A and C. Fit a new tile T against edge B, thereby extending edges A and C. Make the tiled area triangular by fitting a new tile against each of the extended edges.
Case 2: X, Y and Z have pairwise coincident vertices. It follows that these tiles are the same size. Remove Y and Z, thereby reducing the tiled area to a rhombus. Remove the tile at the rhombus vertex opposite X. The remaining area is a pentagon, since n >= 6. Extend the area by resiting Y against X, and Z against Y so that X and Z have external edges aligned. Make the area trapezoidal by fitting a new tile against the area's edge that includes an edge of Y. Fit another tile T against the smaller of the trapezoid's parallel edges.
In each case, we now have n+1 tiles, tiling an equilateral triangle with side length a(n) plus the side of T. As the sides of new and removed tiles can be calculated by adding sides of tiles that stayed in place, the GCD of the sides is unchanged.
(End)

			a(12) = 16:
                                  *
                                 / \
                                +   +
                               /     \
                              +       +
                             /         \
                            +           +
                           /             \
                          +               +
                         /                 \
                        +                   +
                       /                     \
                      +                       +
                     /                         \
                    +                           +
                   /                             \
                  +                               +
                 /                                 \
                *---+---*---+---+---+---+---+---+---*
               / \     / \                         / \
              +   +   +   +                       +   +
             /     \ /     \                     /     \
            *---*---*       +                   +       +
           / \ / \ /         \                 /         \
          +   *---*---+---+---*               +           +
         /     \             / \             /             \
        +       +           +   +           +               +
       /         \         /     \         /                 \
      +           +       +       +       +                   +
     /             \     /         \     /                     \
    +               +   +           +   +                       +
   /                 \ /             \ /                         \
  *---+---+---+---+---*---+---+---+---*---+---+---+---+---+---+---*

Stuart Anderson, An Introduction to Triangled Equilateral Triangles
Ales Drapal and Carlo Hamalainen, An enumeration of equilateral triangle dissections, arXiv:0910.5199 [math.CO], 2009-2010.
Hugo Pfoertner, Illustration of a(15)=39.

Cf. A000931, A001590, A167123, A290653, A290697, A290820.
A014529 gives greatest area of any convex polygon constructable from such triangles.
A089047 is this sequence's equivalent for squares.

Definition modified and 5 terms prepended by Peter Munn, Mar 14 2018

A089046 Least edge-length of a square dissectable into at least n squares in the Mrs. Perkins's quilt problem.

Original entry on oeis.org

1, 2, 2, 2, 3, 3, 4, 5, 6, 8, 10, 14, 18, 24, 30, 40, 54, 71, 92, 121, 155, 210, 266, 360, 476, 642, 833, 1117, 1485, 1967, 2595, 3465, 4534, 5995

Offset: 1

R. K. Guy, Dec 03 2003

An inverse to A005670.
More precisely, a(n) = least k such that A005670(k) >= n. - Peter Munn, Mar 14 2018
It is not clear which terms have been proved to be correct and which are just conjectures. - Geoffrey H. Morley, Aug 29 2012; N. J. A. Sloane, Jul 06 2017
n <= 15 (and possibly 16) proved minimal by J. H. Conway (Conway, J. H. "Re: [math-fun] Mrs. Perkins Quilt - Orders 89, 90 improved over UPIG." math-fun mailing list. October 10, 2003.). The conjectures are best currently known values of a(n) for n > 16. - Stuart E Anderson, Apr 21 2013
A089046 and A089047 are almost certainly correct up to 5000. - Ed Pegg Jr, Jul 06 2017
Deleted terms above 5000. - N. J. A. Sloane, Jul 06 2017
Upper bounds for the next terms in the sequence (which may well be the true values) are 7907, 10293, 13505, 17785, 23239, 31035, 39571, ... - Ed Pegg Jr, Jul 06 2017

H. T. Croft, K. J. Falconer, and R. K. Guy, Section C3 in Unsolved Problems in Geometry, New York: Springer, 1991.
M. Gardner, "Mrs. Perkins's Quilt and Other Square-Packing Problems," Mathematical Carnival, New York: Vintage, 1977.

Stuart E. Anderson, Mrs Perkins's Quilts
J. H. Conway, Mrs. Perkins's Quilt, Proc. Cambridge Phil. Soc. 60, 363-368, 1964.
Ed Pegg, Jr., Mrs. Perkin's Quilts
Ed Pegg Jr., Richard K. Guy, Mrs. Perkins's Quilts (Wolfram Demonstrations Project)
Ed Pegg Jr., Richard K. Guy, Mrs. Perkins's Quilts Notebook source code
G. B. Trustrum, Mrs. Perkins's Quilt, Proc. Cambridge Phil. Soc. 61, 7-11, 1965.
Eric W. 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.

Cf. A005670, A089046, A089047.

More terms from Ed Pegg Jr, Dec 03 2003
Corrected and extended by Ed Pegg Jr, Apr 18 2010
a(24)-a(27) (from Ed Pegg Jr, Jun 15 2010) added by Geoffrey H. Morley, Aug 29 2012
a(28)-a(30) from Stuart E Anderson, Nov 22 2012
Confirmed a(30) as best known, added a(31) as best known. - Stuart E Anderson, Apr 21 2013
Using James Williams recent discoveries of 15 million simple perfect squared squares in orders 31 to 44 I was able to extend the sequence of best currently known values for optimal quilts from a(32) to a(44). - Stuart E Anderson, Apr 21 2013
Using Anderson and Milla's enumeration of order 31 and 32 perfect squared squares, improved conjectures for a(32) and a(33) were obtained - Stuart E Anderson, Sep 16 2013
a(1)-a(19) confirmed by Ed Wynn, 2013. - N. J. A. Sloane, Nov 29 2013
a(29) corrected and further terms added by Ed Pegg Jr, Jul 06 2017

A338861 a(n) is the largest area of a rectangle which can be dissected into n squares with integer sides s_i, i = 1 .. n, and gcd(s_1,...,s_n) = 1.

Original entry on oeis.org

1, 2, 6, 15, 42, 143, 399, 1190, 4209, 10920, 37245, 109886, 339745, 1037186, 3205734, 9784263, 29837784, 93313919, 289627536

Offset: 1

Rainer Rosenthal, Nov 12 2020

A219158 gives the minimum number of squares to tile an i x j rectangle. a(n) is found by checking all rectangles (i,j) for which A219158 has a dissection into n squares.

Due to the potential counterexamples to the minimal squaring conjecture (see MathOverflow link), terms after a(19) have to be considered only as lower bounds: a(20) >= 876696755, a(21) >= 2735106696. - Hugo Pfoertner, Nov 17 2020, Apr 02 2021

			a(6) = 11*13 = 143.
Dissection of the 11 X 13 rectangle into 6 squares:
.
          +-----------+-------------+
          |           |             |
          |           |             |
          |   6 X 6   |    7 X 7    |
          |           |             |
          |           |             |
          +---------+-+             |
          |         +-+-----+-------+
          |  5 X 5  |       |       |
          |         | 4 X 4 | 4 X 4 |
          |         |       |       |
          +---------+-------+-------+
.
a(19) = 16976*17061 = 289627536.
Dissection of the 16976 X 17061 rectangle into 19 squares:
.
       +----------------+-------------+
       |                |             |
       |                |             |
       |                |     7849    |
       |      9212      |             |
       |                |             |
       |                |             |
       |                |------+------|
       |________________|      |      |
       |             |   see   | 4109 |
       |             |Rosenthal|      |
       |             |  link +-+------+
       |     7764    |-------|        |
       |             |       |  5018  |
       |             | 4279  |        |
       |             |       |        |
       +-------------+-------+--------+
.

Stuart Anderson, Catalogues of Simple Perfect Squared Rectangles.
Stuart Anderson, Simple Imperfect Squared Rectangles, orders 9 to 24.
Bertram Felgenhauer, Filling rectangles with integer-sided squares.
MathOverflow, tiling a rectangle with the smallest number of squares, answer by Ed Pegg Jr, Jul 09 2017.
Rainer Rosenthal, Rectangle tiled by 19 squares with maximum area a(19)

Cf. A219158, A340726, A340920.

This sequence and A089047 are effectively analogs for dissecting (or tiling) rectangles and squares respectively. Analogs using equilateral triangular tiles are A014529 and A290821 respectively.

a(11)-a(17) from Hugo Pfoertner based on data from squaring.net website, Nov 17 2020
a(18) from Hugo Pfoertner, Feb 18 2021
a(19) from Hugo Pfoertner, Apr 02 2021

A340919 Sorted sizes of the 55 squares used in the first known squared square of dimension 4205 X 4205 found by Roland Sprague in 1938.

Original entry on oeis.org

13, 29, 35, 39, 50, 52, 65, 78, 87, 91, 104, 116, 117, 130, 140, 143, 145, 174, 182, 195, 203, 221, 232, 234, 247, 261, 270, 286, 290, 299, 305, 312, 319, 325, 340, 375, 406, 429, 435, 493, 522, 551, 565, 575, 615, 638, 665, 667, 696, 705, 725, 957, 1040, 1885, 2320

Offset: 1

Hugo Pfoertner, Feb 16 2021

Stuart Anderson, Roland Percival Sprague (1894-1967), history and bibliography on squaring.net.
James Grime, A Nice Square, Numberphile video, 2017.
David Moews, Squared rectangles, 2007 (provides Bouwcamp code of square).
Roland P. Sprague, Beispiel einer Zerlegung des Quadrats in lauter verschiedene Quadrate, Mathematische Zeitschrift, 45, 607-608, 1939.
R. Sprague, An example of a dissection of the square into pairwise unequal squares, English translation.

Cf. A005670, A006983, A014530, A018835, A089047.

Sum_{k=1..55} a(k)^2 = 4205^2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A217149 Largest possible side length for a perfect squared square of order n; or 0 if no such square exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A014529 Largest convex area that can be tiled with n equilateral triangles whose sides s_k are relatively prime, i.e., gcd(s_1,...,s_n) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A290821 Side length of largest equilateral triangle that can be made from n or fewer equilateral triangles with integer sides s_k, subject to gcd(s_1,s_2,...,s_n) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A089046 Least edge-length of a square dissectable into at least n squares in the Mrs. Perkins's quilt problem.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A338861 a(n) is the largest area of a rectangle which can be dissected into n squares with integer sides s_i, i = 1 .. n, and gcd(s_1,...,s_n) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A340919 Sorted sizes of the 55 squares used in the first known squared square of dimension 4205 X 4205 found by Roland Sprague in 1938.

Views

Author

Keywords

Links

Crossrefs

Formula