The '''density''' of a pattern is the proportion of live [[cell]]s within its [[bounding box]].
The '''density''' of a pattern is the proportion of live [[cell]]s within its [[bounding box]].
==Still Lifes==
==Still lifes==
The general problem of finding the maximum density of an nxn square [[pseudo]] [[still life]] was solved for all n in 2012.<ref name=ref1>{{cite web|url=https://people.eng.unimelb.edu.au/pstuckey/papers/still-life.pdf | title=A Complete Solution to the Maximum Density Still Life Problem | publisher=Geoffrey Chu, Peter J. Stuckey, NICTA Victoria Laboratory, Department of Computing and Information Systems, University of Melbourne, Australia | date=November 8, 2013}}</ref> The maximum densities of square still lifes up to 20×20 were known ten years earlier.<ref>{{cite web|url=https://web.archive.org/web/20130731001049/http://www.ai.sri.com/~nysmith/life |title=Maximum Density Still Life |publisher=Neil Yorke-Smith|date=August 4, 2003}}</ref>
The general problem of finding the maximum density of an {{times|n|n}} square [[pseudo]] [[still life]] was solved for all n in 2012.<ref name=ref1>{{cite web|url=https://people.eng.unimelb.edu.au/pstuckey/papers/still-life.pdf | title=A Complete Solution to the Maximum Density Still Life Problem | publisher=Geoffrey Chu, Peter J. Stuckey, NICTA Victoria Laboratory, Department of Computing and Information Systems, University of Melbourne, Australia | date=November 8, 2013}}</ref> The maximum densities of square still lifes up to {{times|20|20}} were known ten years earlier.<ref>{{cite web|url=https://web.archive.org/web/20130731001049/http://www.ai.sri.com/~nysmith/life |title=Maximum Density Still Life |publisher=Neil Yorke-Smith|date=August 4, 2003}}</ref>
The following table contains maximum density still life information for side lengths through 25.
The following table contains maximum density still life information for side lengths through 25.
Line 65:
Line 65:
*For any side length of the form 3n-1, a segment of [[block agar]] can be used to reach a population of 4n²; to n=4 this is the optimal solution, as can be seen in the above table.
*For any side length of the form 3n-1, a segment of [[block agar]] can be used to reach a population of 4n²; to n=4 this is the optimal solution, as can be seen in the above table.
*The maximum density of an nxn still life is greater than or equal to 1/2 for all finite n>1.<ref name="cgolmc_1">{{citeCGoLMC|section=Section 2.5|nobullet=nobullet}}</ref>
*The maximum density of an {{times|n|n}} still life is greater than or equal to 1/2 for all finite n>1.<ref name="cgolmc_1">{{citeCGoLMC|section=2.5}}</ref>
== Densities of other objects ==
== Densities of other objects ==
Revision as of 05:19, 22 December 2022
The density of a pattern is the proportion of live cells within its bounding box.
The general problem of finding the maximum density of an n × n square pseudostill life was solved for all n in 2012.[1] The maximum densities of square still lifes up to 20 × 20 were known ten years earlier.[2]
The following table contains maximum density still life information for side lengths through 25.
†A055397. After the first few terms, the numbers in this sequence closely approximate the triangular number sequence A000217.
For any side length of the form 3n-1, a segment of block agar can be used to reach a population of 4n²; to n=4 this is the optimal solution, as can be seen in the above table.
The maximum density of an n × n still life is greater than or equal to 1/2 for all finite n>1.[3]
Densities of other objects
The maximum density of a still life agar was proven to be 1/2 by Noam Elkies[4] (this is known as the still life conjecture).
The maximum average density of an oscillating agar is conjectured but not proven to be 1/2. The current upper bound is 8/13, proven by Hartmut Holzwart in 1992.[5]
A055397. After the first few terms, the numbers in this sequence closely approximate the triangular number sequence