The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A181340 Number of compound perfect squared squares of order n up to symmetries of the square and its squared subrectangles. 10
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 16, 46, 143, 412, 941, 2788, 7941, 22413, 62273, 172330, 466508, 1239742, 3257378, 8430928 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,25
COMMENTS
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. A squared rectangle is compound if it contains a smaller squared rectangle. The order of a squared rectangle is the number of constituent squares. - Geoffrey H. Morley, Oct 17 2012
The smallest perfect compound squared square was published by T. H. Willcocks in 1948, has 24 squares and has one rectangle as a sub-dissection; however, it was not until 1982 that A. J. W. Duijvestijn, P. J. Federico and P. Leeuw proved it to be the lowest-order example.
In 2010 Stuart Anderson and Ed Pegg Jr generated all 2-connected minimum degree 3 planar graphs up and including 29 edges, using B. D. McKay and G. Brinkmann's plantri software, then applied electrical node analysis to the graphs to obtain complete counts of compound perfect squares in orders 24, 25, 26, 27 and 28, along with all the members of each equivalence class of each compound square.
In 2011 S. E. Anderson and Stephen Johnson commenced order 29 CPSSs, and processed all plantri generated 2-connected minimum degree 3 planar graph embeddings with up to 15 vertices. This left the largest graph class, the 16 vertex class. In 2012 S. E. Anderson processed the remaining graphs, using the Amazon Elastic Cloud supercomputer and new software which he wrote to find a(29). - Stuart E Anderson, Nov 30 2012
In May 2013 Lorenz Milla and Stuart Anderson enumerated a(30) (CPSSs of order 30), using the same process and software as used on order 29 CPSSs, with the addition of a technique recommended by William Tutte in his writings which resulted in a 3x speed-up of the search for perfect squared squares by factoring the determinant of the Kirchhoff/discrete Laplacian matrix of a graph into a product 2fS, where f is a squarefree number and S is a square number. - Stuart E Anderson, May 26 2013
From June to September 2013, Lorenz Milla further optimized the process and software and completed the computation required to enumerate all CPSSs of order 31 and 32. A second run with enhanced software was undertaken by Milla and Anderson as there was a possibility some CPSSs could have been missed on the first run. The second run found nothing new or different and confirmed the result. - Stuart E Anderson, Sep 29 2013
In April 2014, Jim Williams wrote software and used it to complete the enumeration of CPSS orders 33, 34, 35 and 36. - Stuart E Anderson, May 02 2016
In August 2018, Jim Williams completed the enumeration of CPSS orders 37, 38 and 39. - Stuart E Anderson, September 17 2018.
REFERENCES
J. D. Skinner II, Squared Squares: Who's Who & What's What, published by the author, 1993. [Includes some compound perfect squares up to order 30.]
T. H. Willcocks, Problem 7795 & solution, Fairy Chess Review 7 (1948) 97, 106.
LINKS
S. E. Anderson, Compound Perfect Squared Squares of the Order Twenties, 2013; arXiv:1303.0599 [math.CO], 2013.
G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem., 58 (2007), 323-357.
Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph.
Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph [Cached copy, pdf file only, no active links, with permission]
A. J. W. Duijvestijn, P. J. Federico and P. Leeuw, Compound perfect squares, Amer. Math. Monthly 89 (1982), 15-32. [The lowest order of a compound perfect square is 24.]
N. D. Kazarinoff and R. Weitzenkamp, On the existence of compound perfect squared squares of small order, J. Combin. Theory Ser. B 14 (1973), 163-179. [A compound perfect squared square must contain at least 22 subsquares.]
Eric Weisstein's World of Mathematics, Perfect Square Dissection
EXAMPLE
From Geoffrey H. Morley, Oct 17 2012 (Start):
See MathWorld link for an explanation of Bouwkamp code.
a(24)=1 because all four compound perfect squares of order 24 are equivalent up to symmetries. They have side 175. The Bouwkamp code for one of them is (81,56,38)(18,20)(55,16,3)(1,5,14)(4)(9)(39)(51,30)(29,31,64)(43,8)(35,2)(33). (End)
CROSSREFS
Cf. A217155 (counts symmetries of subrectangles as distinct).
Sequence in context: A023638 A139267 A254855 * A275032 A295533 A220173
KEYWORD
nonn,more,hard
AUTHOR
Stuart E Anderson, Oct 13 2010, Oct 16 2010
EXTENSIONS
Corrected last term from 142 to 143 to include cpss 1170C, added cross reference
Corrected last term from 143 to 144 to include cpss 1224d, incorrectly excluded as a duplicate in the initial count.
Corrected last term from 144 back to 143 after a recount from the original graphs established a bijection between exactly 948 non-isomorphic graphs and 948 isomers in 143 different CPSS arrangements. Gave usual bouwkampcode notation in examples. Removed redundant word "mathematically" from comments. - Stuart E Anderson, Jan 2012
Clarified the definition of 'number' in relation to the 'number' of compound squares, included the definition of 'perfect'. Excluded the trivial dissection from the sequence count. - Stuart E Anderson, May 2012
Definition corrected and offset changed to 1 by Geoffrey H. Morley, Oct 17 2012
a(29) added by Stuart E Anderson, Nov 30 2012
a(30) added by Stuart E Anderson, May 26 2013
a(31)-a(32) added by Stuart E Anderson, Sep 29 2013
a(33)-a(36), enumeration of these orders was completed by Jim Williams in 2014, added by Stuart E Anderson, May 02 2016
a(37)-a(39), enumeration of these orders was completed by Jim Williams in 2018, added by Stuart E Anderson, Sep 17 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 19 14:45 EDT 2024. Contains 372698 sequences. (Running on oeis4.)