login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..61.

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, 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

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)

EXAMPLE

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, ...

...

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 *)

PROG

a(n) = 4^hammingweight((n-1)\2) * if(n%2, 1, 9); \\ Michel Marcus, Oct 08 2018

CROSSREFS

Cf. A000120, A048883, A079315, A122108, A160239, A002063 (last entry in each block)

Sequence in context: A014717 A104728 A058093 * A122846 A248309 A317900

Adjacent sequences:  A164029 A164030 A164031 * A164033 A164034 A164035

KEYWORD

nonn,changed

AUTHOR

John W. Layman, Aug 08 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 13:38 EDT 2018. Contains 316361 sequences. (Running on oeis4.)