A006983 -id:A006983 - cp's OEIS frontend

A220165 Number of nonsquare simple imperfect squared rectangles of order n up to symmetry.

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 9, 33, 104, 280, 948, 3014, 9494, 30302, 98897, 323372, 1080168, 3666666, 12604812, 43734613, 153788715

Offset: 1

Stuart E Anderson, Dec 06 2012

A squared rectangle 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. A squared rectangle is simple if it does not contain a smaller squared rectangle. The order of a squared rectangle is the number of constituent squares.

See A002881 and A006983.

Stuart E. Anderson, Simple Imperfect Squared Rectangles, orders 9 to 24

Cf. A002881, A006983, A002962, A002839.

a(25) from Stuart E Anderson, May 07 2024

a(26) from Stuart E Anderson, Jul 28 2024

A334905 a(n) is the minimum remaining space when a square n X n is tiled with smaller squares with distinct integer sides parallel to the n X n square.

Original entry on oeis.org

1, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 21, 30, 29, 20, 25, 30, 12, 19, 24, 17, 13, 13, 18, 14, 19, 14, 15, 15, 15, 20, 15, 20, 16, 22, 16, 16, 17, 21, 22, 15, 13, 16, 18, 14, 14, 14, 17, 15, 11, 10, 12, 13, 4, 11, 8, 9, 7, 11, 4, 9, 8, 8, 8, 6, 8

Offset: 1

Vitor Pimenta dos Reis Arruda, May 15 2020

nonn

See (Gambini, 1999) for a way to construct the sequence. Actually, one would have to extend Gambini's idea by putting extra 1-sided squares in the list of "usable squares" to allow finding nonzero-waste packings.

			For n=5, squares of sides {1, 4} can be packed inside the container, leading to uncovered area a(5) = 5*5 - (4*4 + 1*1) = 8. The other maximal packable set is composed of the squares sided {1,2,3}, which would lead to uncovered area greater than 8.

Vitor Pimenta dos Reis Arruda, Table of n, a(n) for n = 1..101
I. Gambini, A method for cutting squares into distinct squares, Discrete Applied Mathematics, 98 (1999), 65-80.
Vitor Pimenta dos Reis Arruda, Non trivial decompositions until a(101)
Vitor Pimenta dos Reis Arruda, Luiz Gustavo Bizarro Mirisola, and Nei Yoshihiro Soma, Almost squaring the square: optimal packings for non-decomposable squares, Pesqui. Oper. (2022) Vol. 42.
Giovanni Resta, Illustration of terms a(15)-a(31)
Wikipedia, Squaring the square

Cf. A006983, A002962, A181735, A002839, A228953.

Terms a(17)-a(31) from Giovanni Resta, May 15 2020

A347581 The Barnyard sequence: a(n) is the minimum number of unit length line segments required to enclose areas of 1 through n on a square grid.

Original entry on oeis.org

4, 9, 14, 20, 26, 33, 40, 47, 55, 63

Offset: 1

Scott R. Shannon, Oct 05 2021

The areas of size 1 through n can be created in any order and position, the only requirement being the final number of line segments used to enclose all areas is minimized. It is likely the perimeter of each area of size k, 1 <= k <= n, is the minimum possible for an area of size k, although this is unknown.

See A348149 for the total segments when the number of segments at each step is minimized.

			Example areas using the minimum number of line segments from n = 1 through n = 10 are:
.
   __
  |__|  a(1) = 4
   __ __ __
  |__|__ __|  a(2) = 9
   __ __ __
  |__|__ __|  a(3) = 14
  |__ __ __|
   __ __ __
  |__|__ __|
  |__ __ __|  a(4) = 20
  |     |
  |__ __|
   __ __ __
  |__|__ __|__
  |__ __ __|  |  a(5) = 26
  |     |     |
  |__ __|__ __|
   __ __ __
  |__|__ __|__ __ __
  |__ __ __|  |     |  a(6) = 33
  |     |     |     |
  |__ __|__ __|__ __|
         __ __ __ __
   __ __|__         |
  |__|__ __|__ __ __|
  |__ __ __|  |     |  a(7) = 40
  |     |     |     |
  |__ __|__ __|__ __|
   __ __ __ __ __ __
  |           |     |
  |__ __ __ __|     |
  |        |__ __ __|   a(8) = 47
  |__ __ __|__      |
  |     |  |  |__ __|
  |__ __|__|__ __|__|
   __ __ __ __ __ __ __
  |        |           |
  |        |__ __ __ __|
  |__ __ __|__         |
     |__|__ __|__ __ __|  a(9) = 55
     |__ __ __|  |     |
     |     |     |     |
     |__ __|__ __|__ __|
   __ __ __ __ __ __ __ __
  |         __|__   |     |
  |__ __ __|     |__|__   |
  |        |     |     |__|
  |        |     |     |  |   a(10) = 63
  |__ __ __|__ __|__ __|__|
  |              |     |__|
  |__ __ __ __ __|__ __|
.

Sascha Kurz, Counting polyominoes with minimum perimeter, arXiv:math/0506428 [math.CO], 2015.

Cf. A348149, A001168, A291808, A291809, A328020, A291806, A172477, A006983.

A348149 Variation of the Barnyard sequence A347581: a(n) is the minimum number of unit-length line segments required to enclose areas of 1 through n on a square grid when the number of segments is minimized as each area of incrementing size, starting at 1, is added.

Original entry on oeis.org

4, 9, 14, 20, 26, 33, 40, 48, 55, 64

Offset: 1

Scott R. Shannon, Oct 03 2021

In this variation of A347581 the areas must be added in the order of their sizes, from 1 through n, and as each area is added the minimum possible number of line segments must be used. This forces, for example, the first three areas of size 1, 2 and 3 to form a 2 X 3 block and thus they can never appear in any other arrangement in the final area. This is also true for n up to at least 9 due to the restriction of maximizing the usable edges for the next area. This leads to a(8) and a(10) containing one more line segment than the optimal solutions of A347581.

			Examples of n = 1 to n = 10 are given below. Note that for a(3) the configuration could also consist of the area of size 1 sitting above the area of size 2 with the area of size 3 forming an L-shaped block creating the minimal 2 X 3 block.
.
   __
  |__|  a(1) = 4
   __ __ __
  |__|__ __|  a(2) = 9
   __ __ __
  |__|__ __|  a(3) = 14
  |__ __ __|
   __ __ __
  |__|__ __|
  |__ __ __|  a(4) = 20
  |     |
  |__ __|
   __ __ __
  |__|__ __|__
  |__ __ __|  |  a(5) = 26
  |     |     |
  |__ __|__ __|
   __ __ __
  |__|__ __|__ __ __
  |__ __ __|  |     |  a(6) = 33
  |     |     |     |
  |__ __|__ __|__ __|
         __ __ __ __
   __ __|__         |
  |__|__ __|__ __ __|
  |__ __ __|  |     |  a(7) = 40
  |     |     |     |
  |__ __|__ __|__ __|
         __ __ __ __
        |           |
        |__ __ __ __|
   __ __|__         |
  |__|__ __|__ __ __|  a(8) = 48
  |__ __ __|  |     |
  |     |     |     |
  |__ __|__ __|__ __|
   __ __ __ __ __ __ __
  |        |           |
  |        |__ __ __ __|
  |__ __ __|__         |
     |__|__ __|__ __ __|  a(9) = 55
     |__ __ __|  |     |
     |     |     |     |
     |__ __|__ __|__ __|
      __ __ __ __ __ __ __
     |        |           |
     |        |__ __ __ __|
   __|__ __ __|__         |
  |     |__|__ __|__ __ __|  a(10) = 64
  |     |__ __ __|  |     |
  |     |     |     |     |
  |     |__ __|__ __|__ __|
  |__ __|
.

Sascha Kurz, Counting polyominoes with minimum perimeter, arXiv:math/0506428 [math.CO], 2015.

Cf. A347581, A001168, A291808, A291809, A328020, A291806, A006983.

A220164 Number of simple squared squares of order n up to symmetry.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 5, 15, 19, 57, 72, 275, 499, 1778, 3705, 11318, 24525, 65906, 135599, 333938, 687969, 1681759, 3652677

Offset: 1

Stuart E Anderson, Dec 06 2012

A squared rectangle is a rectangle dissected into a finite number, two or more, of squares, called the elements of the dissection. If no two of these squares have the same size the squared rectangle is called perfect, otherwise it is imperfect. The order of a squared rectangle is the number of constituent squares. The case in which the squared rectangle is itself a square is called a squared square. The dissection is simple if it contains no smaller squared rectangle, otherwise it is compound. This sequence counts both perfect and imperfect simple squared squares up to symmetry.

See A006983 and A217156.

S. E. Anderson, Simple Perfect Squared Squares
S. E. Anderson, Simple Imperfect Squared Squares
S. E. Anderson, Mrs Perkins's Quilts
Eric Weisstein's World of Mathematics, Perfect Square Dissection

Cf. A006983, A002962, A217156, A089046.

a(n) = A006983(n) + A002962(n).

a(13)-a(29) from Stuart E Anderson, Dec 07 2012
Clarified some definitions in comments and added a(30) - Stuart E Anderson, Jun 03 2013
a(31), a(32) added by Stuart E Anderson, Sep 30 2013

A220166 Number of nonsquare simple squared rectangles of order n up to symmetry.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 3, 6, 22, 76, 246, 848, 2889, 9964, 34440, 119875, 420525, 1482802, 5254679, 18713933, 66968081, 240735712

Offset: 1

Stuart E Anderson, Dec 06 2012

A squared rectangle (which may be a square) is a rectangle dissected into a finite number, two or more, of integer sized squares. If no two of these squares have the same size the squared rectangle is perfect. A squared rectangle is simple if it does not contain a smaller squared rectangle. The order of a squared rectangle is the number of constituent squares. This sequence counts nonsquare simple perfect squared rectangles and nonsquare simple imperfect squared rectangles.

See A006983 and A217156 for further links.

S. E. Anderson, Simple Perfect Squared Rectangles [Nonsquare rectangles only]
S. E. Anderson, Simple Imperfect Squared Rectangles [Nonsquare rectangles only]

Cf. A219766, A220165, A002839, A002881.

a(9)-a(24) from Stuart E Anderson Dec 07 2012

A220167 Number of simple squared rectangles of order n up to symmetry.

Original entry on oeis.org

3, 6, 22, 76, 247, 848, 2892, 9969, 34455, 119894, 420582, 1482874, 5254954, 18714432, 66969859, 240739417

Offset: 1

Stuart E Anderson, Dec 06 2012

A squared rectangle is a rectangle dissected into a finite number of integer-sized squares. If no two of these squares are the same size then the squared rectangle is perfect. A squared rectangle is simple if it does not contain a smaller squared rectangle or squared square. The order of a squared rectangle is the number of squares into which it is dissected. [Edited by Stuart E Anderson, Feb 03 2024]

See A006983 and A217156 for references and links.

S. E. Anderson, Simple Perfect Squared Rectangles. [Nonsquare rectangles only]
S. E. Anderson, Simple Perfect Squared Squares.
S. E. Anderson, Simple Imperfect Squared Rectangles. [Nonsquare rectangles only]
S. E. Anderson, Simple Imperfect Squared Squares.
W. T. Tutte, A Census of Planar Maps, Canad. J. Math. 15 (1963), 249-271.

Cf. A002839, A002881, A006983, A002962, A220165, A219766.

a(n) = A002839(n) + A002881(n).
a(n) = A006983(n) + A002962(n) + A220165(n) + A219766(n).
Conjecture: a(n) ~ n^(-5/2) * 4^n / (243*sqrt(Pi)), from "A Census of Planar Maps", p. 267, where William Tutte gave a conjectured asymptotic formula for the number of perfect squared rectangles where n is the number of elements in the dissection (the order). [Corrected by Stuart E Anderson, Feb 03 2024]

a(9)-a(24) from Stuart E Anderson, Dec 07 2012

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

A220165 Number of nonsquare simple imperfect squared rectangles of order n up to symmetry.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A334905 a(n) is the minimum remaining space when a square n X n is tiled with smaller squares with distinct integer sides parallel to the n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A347581 The Barnyard sequence: a(n) is the minimum number of unit length line segments required to enclose areas of 1 through n on a square grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A348149 Variation of the Barnyard sequence A347581: a(n) is the minimum number of unit-length line segments required to enclose areas of 1 through n on a square grid when the number of segments is minimized as each area of incrementing size, starting at 1, is added.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A220164 Number of simple squared squares of order n up to symmetry.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A220166 Number of nonsquare simple squared rectangles of order n up to symmetry.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A220167 Number of simple squared rectangles of order n up to symmetry.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

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