cp's OEIS Frontend

A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton.

%I A164032 #36 Jan 14 2024 14:35:15
%S A164032 1,9,4,36,4,36,16,144,4,36,16,144,16,144,64,576,4,36,16,144,16,144,64,
%T A164032 576,16,144,64,576,64,576,256,2304,4,36,16,144,16,144,64,576,16,144,
%U A164032 64,576,64,576,256,2304,16,144,64,576,64,576,256,2304,64,576,256,2304,256
%N A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton.
%C A164032 This automaton starts with one ON cell and evolves according to the rule that a cell is ON in a given generation if and only if the number of ON cells, among the cell itself and its eight nearest neighbors, was exactly one in the preceding generation.
%H A164032 David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], which is also available at <a href="http://arxiv.org/abs/1004.3036">arXiv:1004.3036v2</a>
%H A164032 N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H A164032 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A164032 It appears that this is the self-generating sequence defined by the following process: start with s={1,9} and repeatedly extend by concatenating s with 4*s, thus obtaining {1,9} -> {1,9,4,36} -> {1,9,4,36,4,36,16,144},... , etc.
%F A164032 Also, it appears that if n=2^k+j, with n>2 and 1<=j<=2^k, then a(n)=4a(j), with a(1)=1, a(2)=9.
%F A164032 From _N. J. A. Sloane_, Jul 21 2014: (Start)
%F A164032 Both of these assertions are not difficult to prove. At generation G = 2^k (k>=1) the ON cells are bounded by a box of edge 2G-1, and in that box there are (G/2)^2 3X3 blocks each containing 9 ON cells (separated by rows of OFF cells of width 1), so a total of a(2^k) = 9*2^(2k-2) ON cells (cf. A002063).
%F A164032 This box is full (more precisely, every cell in it has more than one ON neighbor), and at generation G+1 we have just 4 ON cells which are now at the corners of a box of edge 2G+1. Until the next power of 2 there is no interaction between the configurations that grow at the four corners, and so a(2^k+j) = 4a(j), as conjectured.
%F A164032 In fact this implies an explicit formula for a(n):
%F A164032 a(n) = c*4^wt(floor((n-1)/2)),
%F A164032 where c=1 if n is odd, c=9 if n is even, and wt(i) = A000120(i) is the binary weight function. For example, if n=20, [(n-1)/2]=9 which has weight 2, so a(20) = 9*4^2 = 144. (End)
%e A164032 Can be arranged into blocks of length 2^k:
%e A164032 1,
%e A164032 9,
%e A164032 4, 36,
%e A164032 4, 36, 16, 144,
%e A164032 4, 36, 16, 144, 16, 144, 64, 576,
%e A164032 4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304,
%e A164032 4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304, 16, 144, 64, 576, 64, 576, 256, 2304, 64, 576, 256, 2304, 256, ...
%e A164032 ...
%t A164032 wt[i_] := DigitCount[i, 2, 1];
%t A164032 a[n_] := If[OddQ[n], 1, 9] 4^wt[Floor[(n-1)/2]];
%t A164032 Array[a, 61] (* _Jean-François Alcover_, Oct 08 2018, after _N. J. A. Sloane_ *)
%o A164032 (PARI) a(n) = 4^hammingweight((n-1)\2) * if(n%2, 1, 9); \\ _Michel Marcus_, Oct 08 2018
%Y A164032 Cf. A000120, A048883, A079315, A122108, A160239, A002063 (last entry in each block)
%K A164032 nonn
%O A164032 1,2
%A A164032 _John W. Layman_, Aug 08 2009