# 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...") |
Apple Bottom (talk | contribs) m |
||

(2 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'' |

## Latest revision as of 19:42, 17 March 2018

*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 (*n*^{2}+2*n*+1)/2. Denoting the precise number as *P*(*n*), it is obvious that *P*(*n*) is ½*n*^{2}+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 | 26 | 352 | 46 | 1085 | |||

7 | 28 | 27 | 379 | 47 | 1132 | |||

8 | 36 | Nine blocks | 28 | 407 | 48 | 1181 | ||

9 | 43 | 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*)