Maximum population of a \$n \times n\$ still life in Conway's Game of Life

Question

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

Answer 1

Python 2, 99 bytes

lambda n:n*(27*n+34)/54+(~0x282828a0b0b0b>>n%54&1)-(0x9f4f41e064109edb1e1397137967e232263/5**n+2)%5

Try it online!

The formula in the challenge description works pretty well for \$n<60\$ and is always within 2 of the actual value, so we first calculate the formula:

  n*(27*n+34)/54+~(0x282828a0b0b0b>>n%54&1)
= n*(27*n+34)/54+(~0x282828a0b0b0b>>n%54&1)-2

And add the offset:

  -(0x9f4f41e064109edb1e1397137967e232263/5**n+2)%5+2

The -2 and +2 cancel out

Answer 2

MATL, 32 bytes

UTFZ^!"@GeTTYat3Y6QZ+5:7m=?@svX>

Brute force. Times out for input exceeding 3. Part of the code reused from this answer.

Takes n as input. Try it online!

How it works

U             % Input (implicit): n
TF            % Push [1, 0]
Z^            % Cartesian power: all Cartesian tuples of length n containing
              % 1 or 0. Gives a matrix with n^2 columns, where each row is a
              % Cartesian tuple
!"            % For each row
  @           %   Push current row
  Ge          %   Reshape with n rows (and n columns) 
  TTYa        %   Add a frame of zeros
  t           %   Duplicate
  3Y6QZ+5:7m  %   Perform one iteration of the Game of Life (see linked answer)
  =?          %   If all entries (before and after the iteration) are equal
    @s        %     Push sum of current row (that is, number of active cells)
    vX>       %     Concatenate with previous result, if any, and take maximum
              %   End (implicit)
              % End (implicit)
              % Display (implicit)

Answer 3

JavaScript (Node.js), 122 bytes

n=>n*n/2+17*n/27+1-("1201304124344333343332333333322423223224232332232322323323223"[n]||2+(706447126760203/2**(n%54)&1))|0

Try it online!

Uncompressed table

JavaScript (Node.js), 109 bytes

n=>n*(34+27*n)/54+!(706447126760203/2**(n%54)&1)-[0xbffab022c9fe1aebcdf9b3aabadf0e5376en.toString(5)[n]||2]|0

Try it online!

Indirect port of gsitcia's solution

Answer 4

Charcoal, 57 bytes

ＮθＩ⁻÷×⁺ײ⁷θ³⁴θ⁵⁴⊖§⁺”)⊞E?ü⍘ï″ê&8,⁴&0Ｓ6.¬↶”…”{∨>~iRz÷↙Ｊa”θθ

Try it online! Link is to verbose version of code. Explanation: Based on the formula in the challenge description, but looks up the value to subtract in one of two lookup tables, depending on whether the input is greater than 60 or not.

Ｎθ                              First input as an integer
        ²⁷                      Literal integer 27
       ×                        Multiplied by
          θ                     Input integer
      ⁺                         Plus
           ³⁴                   Literal integer 34
     ×                          Multiplied by
             θ                  Input integer
    ÷                           Integer divided by
              ⁵⁴                Literal integer 54
   ⁻                            Subtract
                   ...          Compressed lookup table for 0..60
                  ⁺             Concatenated with
                       ...      Compressed lookup table for 61..114
                      …         Cyclically extended to length
                          θ     Input integer
                 §              Indexed by
                           θ    Input integer
                ⊖               Decremented
  Ｉ                             Cast to string
                                Implicitly print

Answer 5

Python 3, 285 bytes

lambda n:max(map(len,[q for s in r(n**2+1)for q in combinations([(x,y)for x in r(n)for y in r(n)],s)if{*q}==g(q,n)]))
g=lambda c,n:{(x,y)for x in r(-1,n+1)for y in r(-1,n+1)if sum((q,r)in c for q in[x-1,x,x+1]for r in[y-1,y,y+1])in[[3],[3,4]][(x,y)in c]}
r=range
from itertools import*

Try it online!

Times out pretty fast because it just brute-forces. Pretty sure it's \$O\left(2^{n^2}\right)\$ but it could be worse.

Answer 6

05AB1E, 87 bytes

•1ÏUΓ’∍GTšƒΘQ74₅βvćsZý[Σi—т°/βΩùŠ·ćeeðZGïQ©.†•60в.¥In;17I*27÷+<•6WÁ.‹Ñ•7в.¥I54%å-ª.ÞI<è

Boring approach: hard-codes the values \$\leq60\$, and calculates the values \$\gt60\$ given the formula in the challenge description.

I might try to a brute-force approach later, but 05AB1E overall isn't too great at matrix challenges.

Try it online or verify all test cases.

Explanation:

•1ÏUΓ’∍GTšƒΘQ74₅βvćsZý[Σi—т°/βΩùŠ·ćeeðZGïQ©.†•
             # Push compressed integer 54764668022476930839561631116267184217708747839781677738253594755809981424425189706066485884825983031999
 60в         # Convert it to base-60 as list: [4,2,2,8,2,10,8,7,11,10,12,14,14,15,17,16,19,19,20,22,21,23,25,25,26,27,28,30,30,30,34,32,35,35,35,38,38,38,42,40,43,42,44,46,46,47,49,48,51,51,51,54,54,55,57,56,59,59,59]
    .¥       # Undelta with leading 0: [0,4,6,8,16,18,28,36,43,54,64,76,90,104,119,136,152,171,190,210,232,253,276,301,326,352,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]
I            # Push the input-integer
 n           # Square it
  ;          # Halve it
   17I*      # Push the input*17
       27÷   # Integer-divided by 27
          +  # Add those two together
           < # Decrease it by 1
•6WÁ.‹Ñ•     # Push compressed integer 6607718158603
 7в          # Convert it to base-7 as list: [1,2,5,1,2,5,1,2,6,2,4,2,6,2,6,2]
   .¥        # Undelta with leading 0: [0,1,3,8,9,11,16,17,19,25,27,31,33,39,41,47,49]
     I       # Push the input-integer
      54%    # Modulo-54
         å   # Check if it's in this list
          -  # Subtract that check
ª            # Append it to the earlier list of 60 values
 .Þ          # Infinitely cycle this trailing item
   I<è       # Pop the list and get its 0-based (input-1)'th value
             # (after which it is output implicitly as result)

See this 05AB1E (sections How to compress large integers? and How to compress integer lists?) to understand how the compression works.

Answer 7

Befunge-98 (PyFunge), 236 bytes

 <v.ke0"$+6@LZhw


.
A
U
k3Lf >\z?b+Qw Jr Jv'U		8	h"a'a"Q=s"c-'cf'd!'d"\U"0F='(4"FPSP"
kv>'}*+.:!
$
>:::M2FD\:'FM'FD\I'6%4gFNAAI.1FA



































Code is almost entirely unprintables, many of which get omitted by Stack Exchange's markdown renderer. See the TIO link for the full code.

Brief explanation:

1. The first line is set-up, which first enables the FPSP fingerprint, then pushes 61 as a floating-point number, and a zero as a sentinel value for later. The rest of the first line is a base-124 encoding of the hardcoded numbers for still lifes of value less than 60. The .ke at the beginning of the first line (since code is read in reverse) mean "execute the . instruction 0xe (14) times", printing the values less than 124.
2. The second line just prints the values that are greater than 124 but still hardcoded, until it reaches the sentinel.
3. The third line is a $, which discards the 0 sentinel from earlier. At this point the 61 and then some garbage is left on the stack.
4. The fourth line does the formula part; each / separated segment is one of the terms on the equation.

:::                                 Makes 3 copies of the index being output (leaving 4 on the stack)
   M                                Multiplies the first two together, leaving n^2 and 2 copies of N
    2FD                             Divides by two, leaving N^2/2 and 2 copies of N
       \:                           Swap the top two values and duplicate, leaving 2 copies of N, then n^2 \ 2, then 1 more copy of N
         ' FM' FD                   Do the multiplying by 17 and dividing by 27 for the second term (there's an unprintable character after each ')
                  \I                Swap the top two values, then convert the number to an integer. Stack at this point is N then 17n/27 then n^2/2 then N again
                    '6%4g           Mod N by 54, then look it up in the lookup table in the fourth line of code (which is all unprintables)
                         FN         Convert it from a positive integer to a negative floating-point number
                            AAI.    Add all of the terms on the stack together, convert it to an integer, and output
                                1FA Increment the index on the stack by one for the next iteration.

5. The fifth line of code is a lookup table for whether to subtract one or two. It is never actually executed, merely read using Befunge's ability to look at its own source code.

Try it online!