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, 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.]
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. 30.
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
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: # 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
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