A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton.
1, 9, 4, 36, 4, 36, 16, 144, 4, 36, 16, 144, 16, 144, 64, 576, 4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304, 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
Offset: 1
Keywords
Examples
Can be arranged into blocks of length 2^k: 1, 9, 4, 36, 4, 36, 16, 144, 4, 36, 16, 144, 16, 144, 64, 576, 4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304, 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, ... ...
Links
- David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, 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 arXiv:1004.3036v2
- N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
- Index entries for sequences related to cellular automata
Programs
-
Mathematica
wt[i_] := DigitCount[i, 2, 1]; a[n_] := If[OddQ[n], 1, 9] 4^wt[Floor[(n-1)/2]]; Array[a, 61] (* Jean-François Alcover, Oct 08 2018, after N. J. A. Sloane *)
-
PARI
a(n) = 4^hammingweight((n-1)\2) * if(n%2, 1, 9); \\ Michel Marcus, Oct 08 2018
Formula
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.
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.
From N. J. A. Sloane, Jul 21 2014: (Start)
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).
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.
In fact this implies an explicit formula for a(n):
a(n) = c*4^wt(floor((n-1)/2)),
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)
Comments