A273308 Maximum population of a 2 X n still life in Conway's Game of Life.

0, 4, 4, 6, 8, 8, 10, 12, 12, 14, 16, 16, 18, 20, 20, 22, 24, 24, 26, 28, 28, 30, 32, 32, 34, 36, 36, 38, 40, 40, 42, 44, 44, 46, 48, 48, 50, 52, 52, 54, 56, 56, 58, 60, 60, 62, 64, 64, 66, 68, 68, 70, 72, 72, 74, 76, 76, 78, 80, 80, 82, 84, 84, 86, 88, 88

Offset

1,2

Comments

Although the Chu et al. reference does not discuss this problem explicitly, the same methods in that paper can be used to prove the formula for this sequence.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

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).

LifeWiki, Still life

Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Formula

For n >= 1, a(3*n) = a(3*n-1) = 4*n and a(3*n+1) = 4*n+2.

From Colin Barker, May 24 2016: (Start)

a(n) = a(n-1)+a(n-3)-a(n-4) for n>5.

G.f.: 2*x^2*(2+x^2-x^3) / ((1-x)^2*(1+x+x^2)). (End)

a(n) = A063224(n+1) = A063200(n+1) for n>1. - R. J. Mathar, May 27 2016

Example

a(2) = 4 because the largest number of alive cells in a 2 X 2 still life is 4, which is attained by the block.
a(4) = 6 because the largest number of alive cells in a 2 X 4 still life is 6, which is attained by the snake.

Maple

seq(4*floor((n+1)*(1/3))+2*floor((1/2)*(`mod`(n+1, 3))), n = 2 .. 110);

Mathematica

LinearRecurrence[{1, 0, 1, -1}, {0, 4, 4, 6, 8}, 70] (* Harvey P. Dale, Apr 19 2023 *)

Prog

(PARI) concat(0, Vec(2*x^2*(2+x^2-x^3)/((1-x)^2*(1+x+x^2)) + O(x^50))) \\ Colin Barker, May 24 2016
(Python)
def A273308(n): return n+sum(divmod(n, 3)) if n > 1 else 0 # Chai Wah Wu, Jan 29 2023

Crossrefs

Cf. A019473, A055397.

Sequence in context: A292755 A294021 A200267 * A105790 A338895 A090682

Adjacent sequences: A273305 A273306 A273307 * A273309 A273310 A273311

Keyword

nonn,easy

Author

Nathaniel Johnston, May 19 2016

Status

approved