OFFSET
1,2
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
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)
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
John W. Layman, Apr 15 2011
STATUS
approved