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 maximum densities of square still lifes up to {{times|20|20}} were known in 2002.<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 population of an {{times|n|n}} square [[pseudo]] [[still life]] (<tt>{{OEIS|A055397|tt=tt}}(n)</tt>) 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> It is given by the following function:
<sup>†</sup>After the first few terms, the numbers in this sequence closely approximate the triangular number sequence.<ref>{{LinkWikipedia|Triangular_number|name=Tringular number|nobullet=nobullet}}</ref>
*For any side length of the form 3n-1, a segment of [[block agar]] can be used to reach a population of 4n<sup>2</sup>; to n=4 this is the optimal solution, as can be seen in the above table.
*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>
*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">[[Conway's Game of Life: Mathematics and Construction]], Section 2.5-Still Life Density</ref>
== Densities of other objects ==
== Densities of other objects ==
* The maximum density of a still life agar was proven to be 1/2 by [[Noam Elkies]]<ref>{{cite web|url=https://arxiv.org/abs/math/9905194 |title=The still-Life density problem and its generalizations|author=Noam D. Elkies| accessdate=May 26, 2022| date=May 31, 1999}}</ref> (this is known as the '''still life conjecture''').
* The maximum density of a still life agar was proven to be 1/2 by [[Noam Elkies]]<ref>{{cite web|url=https://arxiv.org/abs/math/9905194 |title=The still-Life density problem and its generalizations|author=Noam D. Elkies| accessdate=May 26, 2022| date=May 31, 1999}}</ref> (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 {{year|1992}}.<ref name="post147457" />
* The maximum average density of an oscillating agar is conjectured but not proven to be 1/2. The current upper bound is 1176/2087≈0.563, proven by [[Keith Amling]] in {{year|2024}}.<ref name="post175245" />
* The density of [[ash]] is [[Achim Flammenkamp's census|approximately 0.0287]] (1 in 35).
* The density of [[ash]] is [[Achim Flammenkamp's census|approximately 0.0287]] (1 in 35).
* By observation, the density of a [[space dust]]y oscillator or spaceship is usually between 0.25 and 0.3.<ref name="post146282" />
* By observation, the density of a [[space dust]]y oscillator or spaceship is usually between 0.25 and 0.3.<ref name="post146282" />
Line 75:
Line 78:
==References==
==References==
<references>
<references>
<ref name="post147457">{{LinkForumThread
<ref name="post175245">{{LinkForumThread
|format = ref
|format = ref
|title = Re: Can we substantiate this claim?
|title = Re: Unproven conjectures
|p = 147457
|p = 175245
|author = Hartmut Holzwart
|author = Keith Amling
|date = June 22, 2022
|date = January 9, 2024
}}</ref>
}}</ref>
<ref name="post146282">{{LinkForumThread
<ref name="post146282">{{LinkForumThread
Line 94:
Line 97:
{{LinkLexicon|lex_d.htm#density}}
{{LinkLexicon|lex_d.htm#density}}
*[https://golhobby.com/patman Maximum Density Still Lifes-PatMan pattern collection] all n=2...200
*[https://golhobby.com/patman Maximum Density Still Lifes-PatMan pattern collection] all n=2...200
*[https://oeis.org/A055397 OEIS: A055397-Maximum population of an n X n stable pattern in Conway's Game of Life]
Latest revision as of 13:17, 2 May 2024
The density of a pattern is the proportion of live cells within its bounding box.
The maximum densities of square still lifes up to 20 × 20 were known in 2002.[1]
The general problem of finding the maximum population of an n × n square pseudostill life (A055397(n)) was solved for all n in 2012.[2] It is given by the following function:
For any side length of the form 3n-1, a segment of block agar can be used to reach a population of 4n2; 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 1176/2087≈0.563, proven by Keith Amling in 2024.[5]