This is OEIS sequence A055397.
In Conway's Game of life, a still life is a pattern that does not change over time. We can see from the rules of Conway's Game of life that, a pattern is a still life if and only if:
- every living cell has exactly two or three living neighbors,
- none of the dead cells have three living neighbors.
Given a positive integer \$n\$, what is the maximum number of living cells of a still life in a \$n \times n\$ bounding box?
The following table shows the results for small \$n\$s: (Screenshot from the book Conway's Game of Life - Mathematics and Construction by Nathaniel Johnston and Dave Greene)
In 2012, G. Chu and P. J. Stuckey gave a complete solution for all \$n\$.
When \$n > 60\$, the results are:
$$\begin{cases} \lfloor n^2/2 + 17n/27 - 2 \rfloor, & \text{ if } n \equiv 0, 1, 3, 8, 9, 11, 16, 17, 19, 25, 27, \\ & \quad \quad \ \ \ \, 31, 33, 39, 41, 47, \text{or } 49 \ (\text{mod } 54) , \text{ and} \\ \lfloor n^2/2 + 17n/27 - 1 \rfloor, & \text{ otherwise}. \end{cases}$$
When \$n \le 60\$, the results are not so regular. They are given in the testcases.
Task
Given a positive integer \$n\$, output the maximum number of living cells of a still life in a \$n \times n\$ bounding box.
As with standard sequence challenges, you may choose to either:
- Take an input \$n\$ and output the \$n\$th term in the sequence.
- Take an input \$n\$ and output the first \$n\$ terms.
- Output the sequence indefinitely, e.g. using a generator.
This is code-golf, so the shortest code in bytes wins.
Testcases
1 0
2 4
3 6
4 8
5 16
6 18
7 28
8 36
9 43
10 54
11 64
12 76
13 90
14 104
15 119
16 136
17 152
18 171
19 190
20 210
21 232
22 253
23 276
24 301
25 326
26 352
27 379
28 407
29 437
30 467
31 497
32 531
33 563
34 598
35 633
36 668
37 706
38 744
39 782
40 824
41 864
42 907
43 949
44 993
45 1039
46 1085
47 1132
48 1181
49 1229
50 1280
51 1331
52 1382
53 1436
54 1490
55 1545
56 1602
57 1658
58 1717
59 1776
60 1835
61 1897
62 1959
63 2022
64 2087
65 2151
66 2218
67 2285
68 2353
69 2422
70 2492
71 2563
72 2636
73 2708
74 2783
75 2858
76 2934
77 3011
78 3090
79 3168
80 3249