A189007 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

1, 4, 8, 16, 16, 32, 32, 64, 32, 64, 64, 128, 64, 128, 128, 256, 64, 128, 128, 256, 128, 256, 256, 512, 128, 256, 256, 512, 256, 512, 512, 1024, 128, 256, 256, 512, 256, 512, 512, 1024, 256, 512, 512, 1024, 512, 1024, 1024, 2048, 256, 512, 512, 1024, 512, 1024, 1024, 2048, 512, 1024, 1024, 2048, 1024, 2048, 2048, 4096, 256, 512, 512, 1024, 512

Offset: 1

Author

John W. Layman, Apr 15 2011

Keywords

• nonn

Comments

The cells are the squares of the standard infinite square grid. All cells are initially OFF and a single cell is turned ON at generation 1. At subsequent generations a cell is ON if and only if exactly one East/West neighbor was ON or exactly one North/South neighbor was ON (or BOTH of those conditions) in the previous generation.

The equivalent Mathematica cellular automaton is obtained with neighborhood weights {{0,1,0},{3,0,3},{0,1,0}}, rule number 186, and initial configuration {{1}}.

Also sequence generated by Rule 84 with neighborhood weights {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}. - Robert Price, Mar 11 2016

Conjecture: a(1) = 1; a(n) = 2^A056791(n-1) for n > 1. - Michael De Vlieger, Nov 02 2022

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..512
• Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 32.
• John W. Layman, Graphs of the automaton for generations 1-15

Crossrefs

Cf. A164982, A165345, A245191.

Programs

Mathematica

ca = CellularAutomaton[{186, {2, {{0, 1, 0}, {3, 0, 3}, {0, 1, 0}}}, {1, 1}}, {{{1}}, 0}, 50-1, -50]; Table[Total[ca[[n]], 2], {n, 1, 50}]

Formula

It appears that this sequence is the limit of the following process. Start with {1,4} and repeatedly perform this set of operations: (1) select the second half H of the sequence; (2) append twice the terms of H, then (3) append four times the terms of H. This gives {1,4} -> {1,4,8,16} -> {1,4,8,16,16,32,32,64} -> {1,4,8,16,16,32,32,64,32,64,64,128,64,128,128,256} -> ... This has been verified for the first 150 terms.

Comment from N. J. A. Sloane, Jul 21 2014: (Start)

It is not difficult to show that the preceding conjecture is correct. In fact one can give an explicit formula for the n-th term. At generation n >= 2, the configuration of ON cells consists of a set of concentric diamonds (see the illustration). The sizes of the diamonds are given by the (n-2)nd term of A245191. Let N = A245191(n-2) = Sum_{i>=0} b_i*2^i. Then the ON cells form a set of diamonds with edge-lengths i+2 for each b_i = 1. The i-th diamond contains 4*(i+1) ON cells, and the total number of ON cells is therefore a(n) = 4*Sum_i (i+1)*b_i. The b_i are given explicitly in A245191.

For example, if n=11, N = A245191(9) = 544 = 2^5 + 2^9, so b_5 = b_9 = 1, there are two diamonds, of side lengths 7 and 11, containing a total of 4*(6+10) = 64 = a(11) ON cells. (End)