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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A160720 Number of "ON" cells at n-th stage in 2-dimensional cellular automaton (see Comments for precise definition). 16
0, 1, 5, 9, 21, 25, 37, 49, 77, 81, 93, 105, 133, 145, 173, 201, 261, 265, 277, 289, 317, 329, 357, 385, 445, 457, 485, 513, 573, 601, 661, 721, 845, 849, 861, 873, 901, 913, 941, 969, 1029, 1041, 1069, 1097, 1157, 1185, 1245, 1305, 1429, 1441, 1469, 1497 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

We work on the vertices of the square grid Z^2, and define the neighbors of a cell to be the four closest cells along the diagonals.

We start at stage 0 with all cells in OFF state.

At stage 1, we turn ON a single cell at the origin.

Once a cell is ON it stays ON.

At each subsequent stage, a cell in turned ON if exactly one of its neighboring cells that are no further from the origin is ON.

The "no further from the origin" condition matters for the first time at stage 8, when only A160721(8) = 28 cells are turned ON, and a(8) = 77. In contrast, A147562(8) = 85, A147582(8) = 36.

This CA also arises as the cross-section in the (X,Y)-plane of the CA in A151776.

In other words, a cell is turned ON if exactly one of its vertices touches an exposed vertex of a ON cell of the previous generation. A special rule for this sequence is that every ON cell has only one vertex that should be considered not exposed: its nearest vertex to the center of the structure.

Analog to the "outward" version (A266532) of the Y-toothpick cellular automaton of A160120 on the triangular grid, but here we have ON cells on the square grid. See also the formula section. - Omar E. Pol, Jan 19 2016

This cellular automaton can be interpreted as the outward version of the Ulam-Warburton two-dimensional cellular automaton (see A147562). - Omar E. Pol, Jun 22 2017

LINKS

JungHwan Min, Table of n, a(n) for n = 0..5000

David Applegate, The movie version

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

FORMULA

Conjecture: a(n) = 1 + 4*(A266532(n) - 1)/3, n >= 1. - Omar E. Pol, Jan 19 2016. This formula is correct! - N. J. A. Sloane, Jan 23 2016

a(n) = 1 + 4*A267700(n-1) = 1 + 2*(A159912(n) - n), n >= 1. - Omar E. Pol, Jan 24 2016

EXAMPLE

If we label the generations of cells turned ON by consecutive numbers we get the cell pattern shown below:

9...............9

.8.8.8.8.8.8.8.8.

..7...7...7...7..

.8.6.6.....6.6.8.

....5.......5....

.8.6.4.4.4.4.6.8.

..7...3...3...7..

.8...4.2.2.4...8.

........1........

.8...4.2.2.4...8.

..7...3...3...7..

.8.6.4.4.4.4.6.8.

....5.......5....

.8.6.6.....6.6.8.

..7...7...7...7..

.8.8.8.8.8.8.8.8.

9...............9

MAPLE

cellOn := [[0, 0]] : bbox := [0, 0, 0, 0]: # llx, lly, urx, ury isOn := proc(x, y, L) local i ; for i in L do if op(1, i) = x and op(2, i) = y then RETURN(true) ; fi; od: RETURN(false) ; end: bb := proc(L) local mamin, i; mamin := [0, 0, 0, 0] ; for i in L do mamin := subsop(1=min(op(1, mamin), op(1, i)), mamin) ; mamin := subsop(2=min(op(2, mamin), op(2, i)), mamin) ; mamin := subsop(3=max(op(1, mamin), op(1, i)), mamin) ; mamin := subsop(4=max(op(2, mamin), op(2, i)), mamin) ; od: mamin ; end: for gen from 2 to 80 do nGen := [] ; print(nops(cellOn)) ; for x from op(1, bbox)-1 to op(3, bbox)+1 do for y from op(2, bbox)-1 to op(4, bbox)+1 do # not yet in list? if not isOn(x, y, cellOn) then

# loop over 4 neighbors of (x, y) non := 0 ; for dx from -1 to 1 by 2 do for dy from -1 to 1 by 2 do # test of a neighbor nearer to origin if x^2+y^2 >= (x+dx)^2+(y+dy)^2 then if isOn(x+dx, y+dy, cellOn) then non := non+1 ; fi; fi; od: od: # exactly one neighbor on: add to nGen if non = 1 then nGen := [op(nGen), [x, y]] ; fi; fi; od: od: # merge old and new generation cellOn := [op(cellOn), op(nGen)] ; bbox := bb(cellOn) ; od: [From R. J. Mathar, Jul 14 2009]

MATHEMATICA

A160720[0]=0; A160720[n_]:=Total[With[{m = n - 1}, BitOr @@ (Function[pos, CellularAutomaton[{FromDigits[Boole[#[[2, 2]] == 1 || Count[Flatten[#], 1] == 1 && Count[Extract[#, pos], 1] == 1] & /@ Tuples[{1, 0}, {3, 3}], 2], 2, {1, 1}}, {{{1}}, 0}, {{{m}}, {-m, m}, {-m, m}}]] /@ Partition[{{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}, 2, 1, 1])], 2] (* JungHwan Min, Jan 23 2016 *)

A160720[0]=0; A160720[n_]:=Total[With[{m = n - 1}, BitOr @@ (CellularAutomaton[{#, 2, {1, 1}}, {{{1}}, 0}, {{{m}}, {-m, m}, {-m, m}}] & /@ {13407603346151304507647333602124270744930157291580986197148043437687863763597662002711256755796972443613438635551055889478487182262900810351549134401372178, 13407603346151304507647333602124270744930157291580986197148043437687863763597777794800494071992396014598447323458909159463152822826940267935557047531012112, 13407603346151304507647333602124270744930157291580986197148043437687863763597777794800494071992396014598447323458909159463152822826940286382301121240563712, 13407603346151304507647333602124270744930157291580986197148043437687863763597662002711256755796972443613438635551055889478487182262900828798293208110923778})], 2] (* JungHwan Min, Jan 23 2016 *)

A160720[0]=0; A160720[n_]:=Total[With[{m = n - 1}, BitOr @@ (CellularAutomaton[{46, {2, ReplacePart[ArrayPad[{{1}}, 1], # -> 2]}, {1, 1}}, {{{1}}, 0}, {{{m}}, All, All}] & /@ Partition[{{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}, 2, 1, 1])], 2] (* JungHwan Min, Jan 24 2016 *)

CROSSREFS

Cf. A139250, A147562, A159912, A160117, A160118, A160120, A160721, A160740, A147562, A160410, A160414, A160412, A160416, A160796, A266532, A267700.

Sequence in context: A244642 A211424 A211428 * A147552 A147562 A162795

Adjacent sequences:  A160717 A160718 A160719 * A160721 A160722 A160723

KEYWORD

nonn

AUTHOR

Omar E. Pol, May 25 2009

EXTENSIONS

Edited by N. J. A. Sloane, Jun 26 2009

More terms from David Applegate, Jul 03 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 February 25 14:46 EST 2018. Contains 299654 sequences. (Running on oeis4.)