Density: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
Atavoidirc (talk | contribs) |
||
| (88 intermediate revisions by 11 users not shown) | |||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
The '''density''' of a pattern is the proportion of live | The '''density''' of a pattern is the proportion of live [[cell]]s within its [[bounding box]]. | ||
The | ==Still lifes== | ||
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> | |||
{| class="wikitable" | 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: | ||
<tt>first=(0,0,4,6,8,16,18,28,36,43,54,64,76,90,104,119,136,152,171,190,210,232,253,276,302,326,353,379,407,437,467,497,531,563,598,<br /> | |||
<span style="opacity: 0">. . . .</span>633,668,706,744,782,824,864,907,949,993,1039,1085,1132,1181,1229,1280,1331,1382,1436,1490,1545,1602,1658,1717,1776,1835)<br />def cells(n):<br /><span style="opacity: 0">. . </span>if n<61:<br /><span style="opacity: 0">. . . . </span>return first[n]<br /><span style="opacity: 0">. . </span>elif n%54 in {0,1,3,8,9,11,16,17,19,25,27,31,33,39,41,47,49}:<br /><span style="opacity: 0">. . . . </span>return ⌊(27*n<sup>2</sup>+34*n)/54⌋-2<br /><span style="opacity: 0">. . </span>else:<br /><span style="opacity: 0">. . . . </span>return ⌊(27*n<sup>2</sup>+34*n)/54⌋-1</tt>. | |||
The following table contains maximum density still life information for side lengths through 25. | |||
{|class="wikitable sortable" style="text-align:center" | |||
|- | |- | ||
! Side length !! Max. density !! Max. population<br/>(example) !! | ! Side length !! Max. density !! Max. population<sup>†</sup><br/>(example) !! Example pattern(s) !! Total patterns | ||
|- | |- | ||
| 1 || 0 || 0 | | 1 || 0 || 0 || || 0 | ||
|- | |- | ||
| 2 || 1 || 4 | | 2 || 1 || 4<br/>[[block]] || {{EmbedViewer|pname=block|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 1 | ||
|- | |- | ||
| 3 || 0. | | 3 || 0.6667 || 6<br/>[[ship]] || {{EmbedViewer|pname=ship|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 1 | ||
|- | |- | ||
| 4 || 0.5 || 8 | | 4 || 0.5 || 8<br/>[[pond]]<br/>[[long ship]] || {{EmbedViewer|pname=pond|viewerconfig= #C [[ THUMBSIZE 3 ]]}}<br>{{EmbedViewer|pname=longship|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 2 | ||
|- | |- | ||
| 5 || 0.64 || 16 | | 5 || 0.64 || 16<br/>{{LinkCatagolue|xs16_rr0rr|name=four blocks|style=raw}} || {{EmbedViewer|pname=4blocks|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 1 | ||
|- | |- | ||
| 6 || 0.5 || 18 | | 6 || 0.5 || 18<br/>two [[long shillelagh]]s<br/>{{LinkCatagolue|xs18_j5mgdbz1101|name=trans-snake-tie with ship|style=raw}}<br/>[https://catagolue.hatsya.com/object/xs18_gbr0rrz11/b3s23 three blocks with ship] || {{EmbedViewer|pname=twolongshillelaghs|viewerconfig= #C [[ THUMBSIZE 3 ]]}} <br />{{EmbedViewer|pname=transsnaketiewithship|viewerconfig= #C [[ THUMBSIZE 3 ]]}} <br />{{EmbedViewer|pname=3blockswithship|viewerconfig= #C [[ THUMBSIZE 3 ]]}} <br />{{EmbedViewer|pname=6x6maxdensitystilllifes|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 9 | ||
|- | |- | ||
| 7 || 0.5714 || 28 || {{EmbedViewer|pname= | | 7 || 0.5714 || 28<br/>{{LinkCatagolue|xs28_db8n9arz3123032|name=tub of snakes|style=raw}} || {{EmbedViewer|pname=7x7maxdensity |viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 1 | ||
|- | |- | ||
| 8 || 0.5625 || 36 | | 8 || 0.5625 || 36<br/>nine blocks || {{EmbedViewer|pname=9blocks|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 1 | ||
|- | |- | ||
| 9 || 0.5309 || 43 || {{EmbedViewer|pname= | | 9 || 0.5309 || 43 || {{EmbedViewer|pname=43cell9x9pseudostilllifes|viewerconfig= #C [[ THUMBSIZE 3 ]]}} || 10 | ||
|- | |- | ||
| 10 || 0.5400 || 54 | | 10 || 0.5400 || 54 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=10x10maxdensity }} || >100 | ||
|- | |- | ||
| 11 || 0.5289 || 64 | | 11 || 0.5289 || 64<br/>sixteen blocks|| {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=11x11maxdensity }} || 1 | ||
|- | |- | ||
| 12 || 0.5278 || 76 | | 12 || 0.5278 || 76 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=12x12maxdensity }} | ||
|- | |- | ||
| 13 || 0.5325 || 90 | | 13 || 0.5325 || 90 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=13x13maxdensity }} | ||
|- | |- | ||
| 14 || 0.5306 || 104 | | 14 || 0.5306 || 104 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=14x14maxdensity }} | ||
|- | |- | ||
| 15 || 0.5289 || 119 | | 15 || 0.5289 || 119 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=15x15maxdensity }} | ||
|- | |- | ||
| 16 || 0.531 || 136 | | 16 || 0.531 || 136 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=16x16maxdensity }} | ||
|- | |- | ||
| 17 || 0.526 || 152 | | 17 || 0.526 || 152 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=17x17maxdensity }} | ||
|- | |- | ||
| 18 || 0.528 || 171 | | 18 || 0.528 || 171 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=18x18maxdensity }} | ||
|- | |- | ||
| 19 || 0.526 || 190 | | 19 || 0.526 || 190 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=19x19maxdensity }} | ||
|- | |- | ||
| 20 || 0.525 || 210 | | 20 || 0.525 || 210 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=20x20maxdensity }} | ||
|- | |||
| 21 || 0.526 || 232 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=21x21maxdensity }} | |||
|- | |||
| 22 || 0.523 || 253 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=22x22maxdensity }} | |||
|- | |||
| 23 || 0.522 || 276 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=23x23maxdensity }} | |||
|- | |||
| 24 || 0.523 || 301 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=24x24maxdensity }} | |||
|- | |||
| 25 || 0.522 || 326 || {{EmbedViewer|viewerconfig= #C [[ THUMBSIZE 3 ]] | pname=25x25maxdensity }} | |||
|} | |} | ||
For any side length of the form 3n-1, a segment of [[block agar]] can be used to reach a population of | *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> | |||
== Densities of other objects == | == Densities of other objects == | ||
* The maximum density of a still life agar | * 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 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 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" /> | ||
==References== | ==References== | ||
<references> | |||
<ref name="post175245">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Unproven conjectures | |||
|p = 175245 | |||
|author = Keith Amling | |||
|date = January 9, 2024 | |||
}}</ref> | |||
<ref name="post146282">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Can we substantiate this claim? | |||
|p = 146282 | |||
|author = David Raucci | |||
|date = May 29, 2022 | |||
}}</ref> | |||
</references> | |||
==External links== | |||
{{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 | ||
Latest revision as of 13:17, 2 May 2024
The density of a pattern is the proportion of live cells within its bounding box.
Still lifes
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 pseudo still life (A055397(n)) was solved for all n in 2012.[2] It is given by the following function:
first=(0,0,4,6,8,16,18,28,36,43,54,64,76,90,104,119,136,152,171,190,210,232,253,276,302,326,353,379,407,437,467,497,531,563,598,
. . . .633,668,706,744,782,824,864,907,949,993,1039,1085,1132,1181,1229,1280,1331,1382,1436,1490,1545,1602,1658,1717,1776,1835)
def cells(n):
. . if n<61:
. . . . return first[n]
. . elif n%54 in {0,1,3,8,9,11,16,17,19,25,27,31,33,39,41,47,49}:
. . . . return ⌊(27*n2+34*n)/54⌋-2
. . else:
. . . . return ⌊(27*n2+34*n)/54⌋-1.
The following table contains maximum density still life information for side lengths through 25.
| Side length | Max. density | Max. population† (example) |
Example pattern(s) | Total patterns |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | |
| 2 | 1 | 4 block |
1 | |
| 3 | 0.6667 | 6 ship |
1 | |
| 4 | 0.5 | 8 pond long ship |
2 | |
| 5 | 0.64 | 16 four blocks |
1 | |
| 6 | 0.5 | 18 two long shillelaghs trans-snake-tie with ship three blocks with ship |
9 | |
| 7 | 0.5714 | 28 tub of snakes |
1 | |
| 8 | 0.5625 | 36 nine blocks |
1 | |
| 9 | 0.5309 | 43 | 10 | |
| 10 | 0.5400 | 54 | >100 | |
| 11 | 0.5289 | 64 sixteen blocks |
1 | |
| 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 |
- 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]
- The density of ash is approximately 0.0287 (1 in 35).
- By observation, the density of a space dusty oscillator or spaceship is usually between 0.25 and 0.3.[6]
References
- ↑ "Maximum Density Still Life". Neil Yorke-Smith (August 4, 2003).
- ↑ "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).
- ↑ Nathaniel Johnston, Dave Greene. Conway's Game of Life: Mathematics and Construction (2022), 2.5.
- ↑ Noam D. Elkies (May 31, 1999). "The still-Life density problem and its generalizations". Retrieved on May 26, 2022.
- ↑ Keith Amling (January 9, 2024). Re: Unproven conjectures (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
External links
- Density at the Life Lexicon
- Maximum Density Still Lifes-PatMan pattern collection all n=2...200