A266977 Number of ON (black) cells in the n-th iteration of the "Rule 78" elementary cellular automaton starting with a single ON (black) cell.

1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36

Offset: 0

Author

Robert Price, Jan 07 2016

Keywords

• nonn
• easy

Comments

Also, a(n-1) is the number of topologically inequivalent opening moves in the Sprouts game on n nodes [Browne]. - Andrey Zabolotskiy, Feb 12 2020

Also the number of symmetrically distinct faces in the 1 x 1 x (n+1) polycube. - Eric W. Weisstein, Sep 02 2022

References

• S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

Links

• Robert Price, Table of n, a(n) for n = 0..1000
• Cameron B. Browne, Boundary Matching for Interactive Sprouts, in: ACG 2015, pp. 147-159, LNCS 9525, Springer, doi:10.1007/978-3-319-27992-3_14.
• Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
• S. Wolfram, A New Kind of Science
• Index entries for sequences related to cellular automata
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1).
• Index to Elementary Cellular Automata

Crossrefs

Cf. A004526, A266974.

Programs

Mathematica

rule=78; rows=20; ca=CellularAutomaton[rule,{{1},0},rows-1,{All,All}]; (* Start with single black cell *) catri=Table[Take[ca[[k]],{rows-k+1,rows+k-1}],{k,1,rows}]; (* Truncated list of each row *) Table[Total[catri[[k]]],{k,1,rows}] (* Number of Black cells in stage n *)

Formula

From Colin Barker, Jan 08 2016 and Apr 16 2019: (Start)

a(n) = (2*n+(-1)^n+7)/4 for n>0.

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

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

From Stefano Spezia, Aug 08 2021: (Start)

E.g.f.: ((4 + x)*cosh(x) + (3 + x)*sinh(x))/2 - 1.

a(n) = 2 + A004526(n) for n > 0. (End)