A273308 - OEIS

%I #24 Apr 19 2023 13:35:03

%S 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,

%T 36,36,38,40,40,42,44,44,46,48,48,50,52,52,54,56,56,58,60,60,62,64,64,

%U 66,68,68,70,72,72,74,76,76,78,80,80,82,84,84,86,88,88

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

%C 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.

%H Colin Barker, <a href="/A273308/b273308.txt">Table of n, a(n) for n = 1..1000</a>

%H G. Chu, P. Stuckey, and M.G. de la Banda, <a href="http://www.csse.monash.edu.au/~mbanda/papers/cp09-sl.pdf">Using relaxations in Maximum Density Still Life</a>, In Proc. of Fifteenth Intl. Conf. on Principles and Practice of Constraint Programming, 258-273 (2009).

%H LifeWiki, <a href="http://www.conwaylife.com/wiki/Still_life">Still life</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,-1).

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

%F From _Colin Barker_, May 24 2016: (Start)

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

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

%F a(n) = A063224(n+1) = A063200(n+1) for n>1. - _R. J. Mathar_, May 27 2016

%e 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.

%e 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.

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

%t LinearRecurrence[{1,0,1,-1},{0,4,4,6,8},70] (* _Harvey P. Dale_, Apr 19 2023 *)

%o (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

%o (Python)

%o def A273308(n): return n+sum(divmod(n,3)) if n > 1 else 0 # _Chai Wah Wu_, Jan 29 2023

%Y Cf. A019473, A055397.

%K nonn,easy

%O 1,2

%A _Nathaniel Johnston_, May 19 2016