Difference between revisions of "User:Apple Bottom/Incubator/Dense stable pattern"
Apple Bottom (talk | contribs) (Created page with "<!-- {{Glossary}} --> A '''dense stable pattern''' is a stable pattern with a high population-to-bounding box ratio. Noam Elkies, in his 1997 paper...") |
DroneBetter (talk | contribs) m (Add apgcodes for those up to 9*9 from https://web.archive.org/web/20160712023902/http://www.argentum.freeserve.co.uk/dense.htm (10*10 has hundreds, so perhaps it will stop there)) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
<!-- {{Glossary}} --> | <!-- {{Glossary}} --> | ||
:''FIXME: Merge into '''[[density]]''''' | |||
A '''dense stable pattern''' is a [[still life|stable]] pattern with a high [[population]]-to-[[bounding box]] ratio. | A '''dense stable pattern''' is a [[still life|stable]] pattern with a high [[population]]-to-[[bounding box]] ratio. | ||
[[Noam Elkies]], in his 1997 paper ''The still-Life density problem and its generalizations'', showed that no | [[Noam Elkies]], in his 1997 paper ''The still-Life density problem and its generalizations'', showed that no infinite stable configuration in [[Conway's Life]] can have a density of more than 0.5; as a corollary, no stable ''n''×''n'' pattern can have a population exceeding (''n''<sup>2</sup>+2''n''+1)/2. Denoting the precise number as ''P''(''n''), it is obvious that ''P''(''n'') is ½''n''<sup>2</sup>+O(''n''). | ||
''FIXME: use Stephen Silver's image to illustrate this'' | ''FIXME: use Stephen Silver's image to illustrate this'' | ||
Line 20: | Line 22: | ||
| 4 || 8 || [[Pond]]; [[Long ship]] || 24 || 301 || || 44 || 993 || | | 4 || 8 || [[Pond]]; [[Long ship]] || 24 || 301 || || 44 || 993 || | ||
|- | |- | ||
| 5 || 16 || Four | | 5 || 16 || {{LinkCatagolue|xs16_rr0rr|patternname=Four blocks|style=raw}} || 25 || 326 || || 45 || 1039 || | ||
|- | |- | ||
| 6 || 18 || | | 6 || 18 || {{LinkCatagolue|xs18_gbr0rrz11|patternname=gbr0rrz11|style=raw}}, {{LinkCatagolue|xs18_jj03lmz11w11|patternname=jj03lmz11w11|style=raw}}, {{LinkCatagolue|xs18_69n8brzx11|patternname=69n8brzx11|style=raw}}, {{LinkCatagolue|xs18_j5mgdbz1101|patternname=j5mgdbz1101|style=raw}}, {{LinkCatagolue|xs18_mljgf9z1w1|patternname=mljgf9z1w1|style=raw}}, {{LinkCatagolue|xs18_j5ka9jz11w11|patternname=j5ka9jz11w11|style=raw}}, {{LinkCatagolue|xs18_i5r8brz11|patternname=i5r8brz11|style=raw}}, {{LinkCatagolue|xs18_j5s2qrz11|patternname=j5s2qrz11|style=raw}}, {{LinkCatagolue|xs18_j9q3pmz11|patternname=j9q3pmz11|style=raw}} || 26 || 352 || || 46 || 1085 || | ||
|- | |- | ||
| 7 || 28 || | | 7 || 28 || {{LinkCatagolue|xs28_db8n9arz3123032|style=raw}} || 27 || 379 || || 47 || 1132 || | ||
|- | |- | ||
| 8 || 36 || Nine | | 8 || 36 || {{LinkCatagolue|xs36_rr0rr0rrz66066066|patternname=Nine blocks|style=raw}} || 28 || 407 || || 48 || 1181 || | ||
|- | |- | ||
| 9 || 43 || | | 9 || 43 || {{LinkCatagolue|xs43_bd0u1f8bdzdb078f1db|patternname=bd0u1f8bdzdb078f1db|style=raw}} {{LinkCatagolue|xs43_j5c9bq1dmzdd1f870bd|patternname=j5c9bq1dmzdd1f870bd|style=raw}}, {{LinkCatagolue|xs43_6t1qb9c5jzdb078f1dd|patternname=6t1qb9c5jzdb078f1dd|style=raw}}, {{LinkCatagolue|xs43_bdg6p78bdzdb078f1db|patternname=bdg6p78bdzdb078f1db|style=raw}}, {{LinkCatagolue|xs43_db8bdge9jzbd1f870bd|patternname=db8bdge9jzbd1f870bd|style=raw}}, {{LinkCatagolue|xs43_db8b9q3pmzbd1f8368d|patternname=db8b9q3pmzbd1f8368d|style=raw}}, {{LinkCatagolue|xs43_6t1qb9c5jzd58f0f95d|patternname=6t1qb9c5jzd58f0f95d|style=raw}}, {{LinkCatagolue|xs43_bd0u1f8bdz39e1dd1db|patternname=bd0u1f8bdz39e1dd1db|style=raw}}, {{LinkCatagolue|xs43_bd0u1f8bdz39d58f1db|patternname=bd0u1f8bdz39d58f1db|style=raw}}, {{LinkCatagolue|xs43_bd0u1f8bdzbd1e95d93|patternname=bd0u1f8bdzbd1e95d93|style=raw}} || 29 || 437 || || 49 || 1229 || | ||
|- | |- | ||
| 10 || 54 || || 30 || 467 || || 50 || 1280 || | | 10 || 54 || || 30 || 467 || || 50 || 1280 || |
Latest revision as of 16:44, 4 March 2023
- FIXME: Merge into density
A dense stable pattern is a stable pattern with a high population-to-bounding box ratio.
Noam Elkies, in his 1997 paper The still-Life density problem and its generalizations, showed that no infinite stable configuration in Conway's Life can have a density of more than 0.5; as a corollary, no stable n×n pattern can have a population exceeding (n2+2n+1)/2. Denoting the precise number as P(n), it is obvious that P(n) is ½n2+O(n).
FIXME: use Stephen Silver's image to illustrate this
Robert Bosch computed precise upper bounds in 2000;[1] Stephen Silver independently computed precise upper bounds for n<11 in February 2000. FIXME: Silver refers to a paper by Barbara M. Smith, which is inaccessible. The following table summarizes the known values up to n=53 ( A055397):
n | P(n) | Attained by | n | P(n) | Attained by | n | P(n) | Attained by |
---|---|---|---|---|---|---|---|---|
1 | 0 | Vacuum | 21 | 232 | 41 | 864 | ||
2 | 4 | Block | 22 | 253 | 42 | 907 | ||
3 | 6 | Ship | 23 | 276 | 43 | 949 | ||
4 | 8 | Pond; Long ship | 24 | 301 | 44 | 993 | ||
5 | 16 | Four blocks | 25 | 326 | 45 | 1039 | ||
6 | 18 | gbr0rrz11, jj03lmz11w11, 69n8brzx11, j5mgdbz1101, mljgf9z1w1, j5ka9jz11w11, i5r8brz11, j5s2qrz11, j9q3pmz11 | 26 | 352 | 46 | 1085 | ||
7 | 28 | xs28_db8n9arz3123032 | 27 | 379 | 47 | 1132 | ||
8 | 36 | Nine blocks | 28 | 407 | 48 | 1181 | ||
9 | 43 | bd0u1f8bdzdb078f1db j5c9bq1dmzdd1f870bd, 6t1qb9c5jzdb078f1dd, bdg6p78bdzdb078f1db, db8bdge9jzbd1f870bd, db8b9q3pmzbd1f8368d, 6t1qb9c5jzd58f0f95d, bd0u1f8bdz39e1dd1db, bd0u1f8bdz39d58f1db, bd0u1f8bdzbd1e95d93 | 29 | 437 | 49 | 1229 | ||
10 | 54 | 30 | 467 | 50 | 1280 | |||
11 | 64 | 31 | 497 | 51 | 1331 | |||
12 | 76 | 32 | 531 | 52 | 1382 | |||
13 | 90 | 33 | 563 | 53 | 1436 | |||
14 | 104 | 34 | 598 | |||||
15 | 119 | 35 | 633 | |||||
16 | 136 | 36 | 668 | |||||
17 | 152 | 37 | 706 | |||||
18 | 171 | 38 | 744 | |||||
19 | 190 | 39 | 782 | |||||
20 | 210 | 40 | 824 |
FIXME: add Stephen Silver's illustrations for n up to 13
OEIS: "For n>=55, floor(n^2/2 + 17*n/27 - 2) <= a(n) <= ceil(n^2/2 + 17*n/27 - 2), which gives all values of this sequence within +/- 1."
References
- ↑ Robert Bosch, Maximum Density Stable Patterns in Variants of Conway's Game of Life, Operations Research Letters 27(1), 7-11, (2000)
Further reading
FIXME: fmt
- G. Chu and P. J. Stuckey, A complete solution to the Maximum Density Still Life Problem, Artificial Intelligence, 184:1-16 (2012).
- G. Chu, K. E. Petrie, and N. Yorke-Smith, Constraint Programming to Solve Maximal Density Still Life, In Game of Life Cellular Automata chapter 10, A. Adamatzky, Springer-UK, 99-114 (2010).
- G. Chu, P. Stuckey, and M.G. de la Banda, Using relaxations in Maximum Density Still Life, In Proc. of Fifteenth Intl. Conf. on Principles and Practice of Constraint Programming, 258-273 (2009).
External links
- Stephen Silver, Dense Stable Patterns (archived) (FIXME: live copy? Also, fmt)