A160721 -id:A160721 - cp's OEIS frontend

A160720 Number of "ON" cells at n-th stage in 2-dimensional cellular automaton (see Comments for precise definition).

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

Offset: 0

Omar E. Pol, May 25 2009

nonn

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

			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

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

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

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

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

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

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

More terms from David Applegate, Jul 03 2009

A151836 First differences of A147552.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 12, 28, 4, 12, 12, 28, 20, 28, 36, 68, 4, 12, 12, 28, 20, 28, 36, 68, 36, 28, 36, 68, 68, 76, 100, 172, 12, 28, 12, 28, 20, 28, 36, 68, 36, 28, 36, 68, 68, 76, 100, 172, 76, 28, 36, 68, 68, 76

Offset: 1

N. J. A. Sloane, Jul 13 2009

nonn

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.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A139250, A147552, A151837, A160721.

Terms after a(30) from Nathaniel Johnston, Mar 27 2011

A160723 First differences of A160722.

Original entry on oeis.org

1, 4, 4, 10, 4, 10, 10, 22, 4, 10, 10, 22, 10, 22, 22, 46, 4, 10, 10, 22, 10, 22, 22, 46, 10, 22, 22, 46, 22, 46, 46, 94, 4, 10, 10, 22, 10, 22, 22, 46, 10, 22, 22, 46, 22, 46, 46, 94, 10, 22, 22, 46, 22, 46, 46, 94, 22, 46, 46, 94, 46, 94, 94, 190

Offset: 1

Omar E. Pol, May 25 2009

nonn

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.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A139250, A139251, A160720, A160721, A160722.

a(n) = 3*A001316(n-1) - 2

Formula and more terms from Max Alekseyev, Sep 08 2011

A256257 6 times numbers of Gould's sequence A001316.

Original entry on oeis.org

6, 12, 12, 24, 12, 24, 24, 48, 12, 24, 24, 48, 24, 48, 48, 96, 12, 24, 24, 48, 24, 48, 48, 96, 24, 48, 48, 96, 48, 96, 96, 192, 12, 24, 24, 48, 24, 48, 48, 96, 24, 48, 48, 96, 48, 96, 96, 192, 24, 48, 48, 96, 48, 96, 96, 192, 48, 96, 96, 192, 96, 192, 192, 384, 12, 24, 24, 48, 24, 48, 48, 96, 24, 48, 48, 96, 48, 96, 96, 192

Offset: 0

Omar E. Pol, Mar 20 2015

Also, number of triangular cells turned ON at (n+1)-st stage in the structure of A256256.

First differences of A256256.

			Written as an irregular triangle in which the row lengths are the terms of A011782, the sequence begins:
6;
12;
12, 24;
12, 24, 24, 48;
12, 24, 24, 48, 24, 48, 48, 96;
12, 24, 24, 48, 24, 48, 48, 96, 24, 48, 48, 96, 48, 96, 96, 192;
...

Cf. A001316, A011782, A047999, A048896, A117973, A151787, A160713, A160721, A256256.

a(n) = 6*A001316(n) = 3*A117973(n) = 2*A160713(n).

a(n) = 12*A048896(n-1), n >= 1.

A262621 First differences of A262620.

Original entry on oeis.org

1, 4, 12, 4, 28, 20, 12, 4, 60, 52, 44, 36, 28, 20, 12, 4, 124, 116, 108, 100, 92, 84, 76, 68, 60, 52, 44, 36, 28, 20, 12, 4, 252, 244, 236, 228, 220, 212, 204, 196, 188, 180, 172, 164, 156, 148, 140, 132, 124, 116, 108, 100, 92, 84, 76, 68, 60, 52, 44, 36, 28, 20, 12, 4, 508, 500, 492, 484, 476, 468, 460, 452, 444, 436

Offset: 0

Omar E. Pol, Nov 03 2015

Number of cells turned "ON" at n-th stage of cellular automaton of A262620.

			With the terms written as an irregular triangle in which row lengths are the terms of A011782 the sequence begins:
1;
4;
12, 4;
28, 20, 12, 4;
60, 52, 44, 36, 28, 20, 12, 4;
124, 116, 108, 100, 92, 84, 76, 68, 60, 52, 44, 36, 28, 20, 12, 4;
...

Cf. A147582, A160721, A261693, A262620.

Row sums give A000302. Row lengths give A011782. Right border gives A123932. Column 1 is A173033.

a(n) = 4 * A261693(n), n >= 1.

A266533 First differences of A266532.

Original entry on oeis.org

1, 3, 3, 9, 3, 9, 9, 21, 3, 9, 9, 21, 9, 21, 21, 45, 3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93, 3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93, 9, 21, 21, 45, 21, 45, 45, 93, 21, 45, 45, 93, 45, 93, 93, 189, 3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93

Offset: 1

David Applegate and Omar E. Pol, Jan 18 2016

Number of Y-toothpicks added at n-th stage in the structure of A266532.

A simplified version of A160121.

			Written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
1;
3;
3, 9;
3, 9, 9, 21;
3, 9, 9, 21, 9, 21, 21, 45;
3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93;
...
Observation: at least the first 11 terms of the right border coincide with A068156.

David Applegate, The movie version
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata
Index entries for sequences related to toothpick sequences

Cf. A000120, A011782, A038573, A068156. A139251, A147582, A160121, A151710, A160721, A266532, A267701.

a(1) = 1. It appears that a(n) = 3*A038573(n-1), n >= 2.

A256139 First differences of A256138.

Original entry on oeis.org

1, 4, 4, 12, 4, 12, 20, 28, 4, 12, 20, 36, 36, 28, 52, 60, 4, 12, 20, 36, 36, 36, 68, 100, 68, 28, 52, 92, 108, 76, 124, 124, 4, 12, 20, 36, 36, 36, 68, 100, 68, 36, 68, 116, 148, 132, 164, 228, 132, 28, 52, 92, 108, 108, 172, 268, 236, 108, 124, 220, 276, 196, 276, 252

Offset: 0

Omar E. Pol, Mar 20 2015

Number of cells turned ON at n-th stage in the structure of A256138.

First differs from A169708 at a(11).

			Written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
1;
4;
4,12;
4,12,20,28;
4,12,20,36,36,28,52,60;
4,12,20,36,36,36,68,100,68,28,52,92,108,76,124,124;
4,12,20,36,36,36,68,100,68,36,68,116,148,132,164,228,132,28,52,92,108,108,172,268,236,108,124,220,276,196,276,252;
...
It appears that the right border gives A173033.

Cf. A028399, A011782, A151723, A151724, A160721, A169708, A170898, A170905, A173033, A256138.

a(n) = 2*A151724(n+1)/3, n >= 1.

cp's OEIS Frontend

A160720 Number of "ON" cells at n-th stage in 2-dimensional cellular automaton (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A151836 First differences of A147552.

Views

Author

Keywords

Links

Crossrefs

Extensions

A160723 First differences of A160722.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A256257 6 times numbers of Gould's sequence A001316.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A262621 First differences of A262620.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A266533 First differences of A266532.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A256139 First differences of A256138.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula