The general problem of finding the maximum density of an nxn square [[pseudo]] [[still life]] was solved for all n in 2012.<ref>{{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 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 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>{{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 density of an nxn still life is greater than or equal to 1/2 for all finite n>1.<ref name=ref1 />
== Densities of other objects ==
== Densities of other objects ==
Revision as of 20:49, 6 July 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 nxn 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.
†After the first few terms, the numbers in this sequence closely approximate the triangular number sequence.[3]
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.[1]
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]