Density: Difference between revisions
Jump to navigation
Jump to search
added zip link for 20-246 |
25 (that's enough) |
||
| Line 5: | Line 5: | ||
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>{{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 | The following table contains maximum density still life information for side lengths through 25. | ||
{|class="wikitable" style="text-align:center" | {|class="wikitable" style="text-align:center" | ||
| Line 58: | Line 58: | ||
|- | |- | ||
| 24 || 0.523 || 301 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=24x24maxdensity }} | | 24 || 0.523 || 301 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=24x24maxdensity }} | ||
|- | |||
| 25 || 0.522 || 326 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=25x25maxdensity }} | |||
|} | |} | ||
Revision as of 00:39, 29 June 2022
The density of a pattern is the proportion of live cells within its bounding box.
Still Lifes
The general problem of finding the maximum density of an nxn square pseudo still 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.
| Side length | Max. density | Max. population† (example) |
Example pattern(s) |
|---|---|---|---|
| 1 | 0 | 0 | |
| 2 | 1 | 4 block |
|
| 3 | 0.6 | 6 ship |
|
| 4 | 0.5 | 8 pond long ship |
|
| 5 | 0.64 | 16 four blocks |
|
| 6 | 0.5 | 18 two long shillelaghs trans-snake-tie with ship three blocks with ship |
|
| 7 | 0.5714 | 28 | |
| 8 | 0.5625 | 36 nine blocks |
|
| 9 | 0.5309 | 43 | |
| 10 | 0.5400 | 54 | |
| 11 | 0.5289 | 64 sixteen blocks |
|
| 12 | 0.5278 | 76 | |
| 13 | 0.5325 | 90 | |
| 14 | 0.5306 | 104 | |
| 15 | 0.5289 | 119 | |
| 16 | 0.531 | 136 | |
| 17 | 0.526 | 152 | |
| 18 | 0.528 | 171 | |
| 19 | 0.526 | 190 | |
| 20 | 0.525 | 210 | |
| 21 | 0.526 | 232 | |
| 22 | 0.523 | 253 | |
| 23 | 0.522 | 276 | |
| 24 | 0.523 | 301 | |
| 25 | 0.522 | 326 |
†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.
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]
- The density of ash is approximately 0.0287 (1 in 35).[6]
- By observation, the density of a space dusty oscillator or spaceship is usually between 0.25 and 0.3.[7]
References
- ↑ "A Complete Solution to the Maximum Density Still Life Problem". Geoffrey Chu, Peter J. Stuckey, NICTA Victoria Laboratory, Department of Computing and Information Systems, University of Melbourne, Australia (November 8, 2013).
- ↑ "Maximum Density Still Life". Neil Yorke-Smith (August 4, 2003).
- ↑ Tringular number at Wikipedia
- ↑ Noam D. Elkies (May 31, 1999). "The still-Life density problem and its generalizations". Retrieved on May 26, 2022.
- ↑ Hartmut Holzwart (June 22, 2022). Re: Can we substantiate this claim? (discussion thread) at the ConwayLife.com forums
- ↑ Oscar Cunningham (January 17, 2018). Re: Life Thermodynamics (discussion thread) at the ConwayLife.com forums
- ↑ David Raucci (May 29, 2022). Re: Can we substantiate this claim? (discussion thread) at the ConwayLife.com forums