Difference between revisions of "User:Apple Bottom/Incubator/Dense stable pattern"

From LifeWiki
Jump to navigation Jump to search
m
 
(One intermediate revision by one other user not shown)
Line 4: Line 4:
 
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 [[still life]] in [[Conway's Life]] can have a density of more than 0.5; as a corollary, no stable n&times;''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 &frac12;''n''<sup>2</sup>+O(''n'').
+
[[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''&times;''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 &frac12;''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 (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 (OEISicon light 11px.png 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

  1. ↑ 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

Retrieved from "https://www.conwaylife.com/w/index.php?title=User:Apple_Bottom/Incubator/Dense_stable_pattern&oldid=45277"