A079317 -id:A079317 - cp's OEIS frontend

A079315 Number of cells that change from OFF to ON at stage n of the cellular automaton described in A079317.

0, 1, 4, 4, 12, 4, 20, 12, 44, 4, 52, 12, 76, 12, 100, 36, 172, 4, 180, 12, 204, 12, 228, 36, 300, 12, 324, 36, 396, 36, 468, 108, 684, 4, 692, 12, 716, 12, 740, 36, 812, 12, 836, 36, 908, 36, 980, 108, 1196, 12, 1220, 36, 1292, 36, 1364, 108, 1580, 36, 1652, 108, 1868

Offset: 0

N. J. A. Sloane, Feb 12 2003

Start with cell (0,0) ON; at each succeeding stage the cells that share exactly one edge with an active cell change their state.

This is not the CA discussed by Singmaster in the reference given in A079314. That was an error based on my misreading of the paper. - N. J. A. Sloane, Aug 05 2009

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

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.]
D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A079316-A079319, A147582, A151914, A151917, A151920, A151921, A139250.

wt[n_] := DigitCount[n, 2, 1];
A147582[n_] := If[n == 1, 1, 4*3^(wt[n-1]-1)];
A151914[n_] := Switch[n, 0, 0, 1, 4, _, (8/3)*Sum[3^wt[i], {i, 1, n-1}]+4];
a[n_] := If[OddQ[n], A147582[(n-1)/2+1], A151914[n/2]];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Apr 21 2024 *)

a(2n+1) = A147582(n+1), a(2n) = A151914(n).

More terms from John W. Layman, Oct 30 2003

Edited by N. J. A. Sloane, Aug 05 2009

A079316 Number of first-quadrant cells (including the two boundaries) that are ON at stage n of the cellular automaton described in A079317.

Original entry on oeis.org

1, 3, 3, 7, 5, 11, 9, 21, 11, 25, 15, 35, 19, 45, 29, 73, 31, 77, 35, 87, 39, 97, 49, 125, 53, 135, 63, 163, 73, 191, 101, 273, 103, 277, 107, 287, 111, 297, 121, 325, 125, 335, 135, 363, 145, 391, 173, 473, 177, 483, 187, 511, 197, 539, 225, 621, 235, 649, 263, 731

Offset: 0

N. J. A. Sloane, Feb 12 2003

Start with cell (0,0) active; at each succeeding stage the cells that share exactly one edge with an active cell change their state.
The pattern has 4-fold symmetry; sequence just counts cells in one quadrant.
This is not the CA discussed by Singmaster in the reference given in A079314. That was an error based on my misreading of the paper. - N. J. A. Sloane, Aug 05 2009

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

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.]
D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A079317, A151922, A151923.

M=matrix(101,101); M[1,1]=1; for(s=1,100, c=[]; a=M[1,1]; for(x=2,100, for(y=2,100, a+=M[x,y]; if(M[x-1,y]+M[x+1,y]+M[x,y-1]+M[x,y+1]==1, c=concat(c,[[x,y]]) )); a+=M[x,1]+M[1,x]; if(M[x,2]==0 && M[x-1,1]+M[x+1,1]==1, c=concat(c,[[x,1]]) ); if(M[2,x]==0 && M[1,x-1]+M[1,x+1]==1, c=concat(c,[[1,x]]) )); print1(a,", "); for(i=1,length(c),M[c[i][1],c[i][2]]=1-M[c[i][1],c[i][2]]) ) \\ Max Alekseyev, Feb 02 2007

More terms from Max Alekseyev, Feb 02 2007

Edited by N. J. A. Sloane, Aug 05 2009

A151921 Net gain in number of ON cells at stage n of the cellular automaton described in A079317.

Original entry on oeis.org

0, 1, 4, 0, 12, -8, 20, -8, 44, -40, 52, -40, 76, -64, 100, -64, 172, -168, 180, -168, 204, -192, 228, -192, 300, -288, 324, -288, 396, -360, 468, -360, 684, -680, 692, -680, 716, -704, 740, -704, 812, -800, 836, -800, 908, -872, 980, -872, 1196

Offset: 0

N. J. A. Sloane, Aug 05 2009, Aug 06 2009

sign

Start with cell (0,0) ON; at each succeeding stage the cells that share exactly one edge with an active cell change their state.

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. A079317, A079315, A139250, A151914, A147582.

If n is even, a(n) = A079315(n) = A151914(n/2); if n is odd, a(n) = A147582((n+1)/2) - A151914((n-1)/2).

First differences of A079317.

A079314 Number of first-quadrant cells (including the two boundaries) born at stage n of the Holladay-Ulam cellular automaton.

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 4, 10, 2, 4, 4, 10, 4, 10, 10, 28, 2, 4, 4, 10, 4, 10, 10, 28, 4, 10, 10, 28, 10, 28, 28, 82, 2, 4, 4, 10, 4, 10, 10, 28, 4, 10, 10, 28, 10, 28, 28, 82, 4, 10, 10, 28, 10, 28, 28, 82, 10, 28, 28, 82, 28, 82, 82, 244, 2, 4, 4, 10, 4, 10, 10, 28, 4, 10, 10, 28, 10, 28, 28, 82, 4

Offset: 0

N. J. A. Sloane, Feb 12 2003

See the main entry for this CA, A147562, for further information.
When I first read the Singmaster MS in 2003 I misunderstood the definition of the CA. In fact once cells are ON they stay ON. The other version, when cells can change state from ON to OFF, is described in A079317. - N. J. A. Sloane, Aug 05 2009
The pattern has 4-fold symmetry; sequence just counts cells in one quadrant.

			From _Omar E. Pol_, Jul 18 2009: (Start)
If written as a triangle:
  1;
  2;
  2,4;
  2,4,4,10;
  2,4,4,10,4,10,10,28;
  2,4,4,10,4,10,10,28,4,10,10,28,10,28,28,82;
  2,4,4,10,4,10,10,28,4,10,10,28,10,28,28,82,4,10,10,28,10,28,28,82,10,28;...
Rows converge to A151712.
(End)

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

Paolo Xausa, Table of n, a(n) for n = 0..10000
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.]
Omar E. Pol, Illustration of initial terms (Overlapping squares) [From _Omar E. Pol_, Nov 20 2009]
D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015

Cf. A147582, A079315, A079316, A079317, A079318, A079319, A151713, A139250.

Cf. A151712, A151922, A160407.

A079314list[nmax_]:=Join[{1},3^(DigitCount[Range[nmax],2,1]-1)+1];A079314list[100] (* Paolo Xausa, Jun 29 2023 *)

For n > 0, a(n) = 3^(A000120(n)-1) + 1.
For n > 0, a(n) = A147582(n)/4 + 1.
Partial sums give A151922. [Omar E. Pol, Nov 20 2009]

Edited by N. J. A. Sloane, Aug 05 2009

A079319 a(0) = 1; for n >= 1, a(n) = 4*a(n-1) - (2^n-1).

Original entry on oeis.org

1, 3, 9, 29, 101, 373, 1429, 5589, 22101, 87893, 350549, 1400149, 5596501, 22377813, 89494869, 357946709, 1431721301, 5726754133, 22906754389, 91626493269, 366504924501, 1466017600853, 5864066209109, 23456256447829

Offset: 0

N. J. A. Sloane, Feb 12 2003

Paolo Xausa, Table of n, a(n) for n = 0..1000
David Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7. Also cached copy, included with permission.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A079314, A079315, A079316, A079317, A079318.

Records in A085194.

A079319list[nmax_]:=LinearRecurrence[{7,-14,8},{1,3,9},nmax+1];A079319list[50] (* Paolo Xausa, Jul 30 2023 *)

PARI
```
a(n)=if(n<0,0,2^n+(4^n-1)/3)
```

A079319=lambda n: 2**n + 4**n//3 # M. F. Hasler, May 28 2024

a(n) = 2^n + (4^n-1)/3, n>=0.
a(n) = Sum_{i = 0..2^n - 1} A079314(i).
G.f.: (1-4x+2x^2)/((1-x)(1-2x)(1-4x)).

A079318 a(0) = 1; for n > 0, a(n) = (3^(A000120(n)-1) + 1)/2.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 5, 1, 2, 2, 5, 2, 5, 5, 14, 1, 2, 2, 5, 2, 5, 5, 14, 2, 5, 5, 14, 5, 14, 14, 41, 1, 2, 2, 5, 2, 5, 5, 14, 2, 5, 5, 14, 5, 14, 14, 41, 2, 5, 5, 14, 5, 14, 14, 41, 5, 14, 14, 41, 14, 41, 41, 122, 1, 2, 2, 5, 2, 5, 5, 14, 2, 5, 5, 14, 5, 14, 14, 41, 2, 5, 5, 14, 5, 14, 14, 41, 5, 14, 14

Offset: 0

N. J. A. Sloane, Feb 12 2003

			From _Omar E. Pol_, Jul 18 2009: (Start)
If written as a triangle:
1;
1;
1,2;
1,2,2,5;
1,2,2,5,2,5,5,14;
1,2,2,5,2,5,5,14,2,5,5,14,5,14,14,41;
1,2,2,5,2,5,5,14,2,5,5,14,5,14,14,41,2,5,5,14,5,14,14,41,5,14,14,41,14,41,41,122;
(End)

Alex Fink, Aviezri S. Fraenkel and Carlos Santos, LIM is not slim, International Journal of Game Theory, May 2013
David Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

Amiram Eldar, Table of n, a(n) for n = 0..10000
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.]
David Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A079314, A079315, A079316, A079317, A079318, A079319.

Cf. A010060, A092255.

a[n_] := (3^(DigitCount[n, 2, 1] - 1) + 1)/2; a[0] = 1; Array[a, 100, 0] (* Amiram Eldar, Jul 29 2023 *)

For n>=1, a(n) mod 2 = A010060(n), the Thue-Morse sequence - Benoit Cloitre, Mar 23 2004

a(n) = Sum_{i+j+k=n, 0<=k<=j<=i<=n} (n!/(i!*j!*k!) mod 2). - Benoit Cloitre, Jul 02 2004

A151914 a(0)=0, a(1)=4; for n>=2, a(n) = (8/3)*(Sum_{i=1..n-1} 3^wt(i)) + 4, where wt() = A000120().

Original entry on oeis.org

0, 4, 12, 20, 44, 52, 76, 100, 172, 180, 204, 228, 300, 324, 396, 468, 684, 692, 716, 740, 812, 836, 908, 980, 1196, 1220, 1292, 1364, 1580, 1652, 1868, 2084, 2732, 2740, 2764, 2788, 2860, 2884, 2956, 3028, 3244, 3268, 3340, 3412, 3628, 3700, 3916, 4132, 4780

Offset: 0

N. J. A. Sloane, Aug 05 2009, Aug 06 2009

Also, total number of "ON" "subcells" at n-th stage in two of the four wedges of the "Ulam-Warburton" two-dimensional cellular automaton of A147562, but including the central "ON" cell. Assume that every "ON" cell contains four "subcells". - Omar E. Pol, Feb 22 2015

Cf. A079315, A079317, A147562, A151917, A151920.

a(n) = A079315(2n).
For n>=2, a(n) = 8*A151920(n-2) + 4.
a(n) = 4*A151917(n). - Omar E. Pol, Feb 22 2015

A273409 Partial sums of the number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 678", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 6, 11, 28, 37, 66, 87, 152, 177, 254, 291, 404, 453, 602, 687, 944, 1033, 1302, 1403, 1708, 1821, 2162, 2311, 2760, 2921, 3406, 3603, 4196, 4429, 5130, 5471, 6496, 6841, 7878, 8235, 9308, 9677, 10786, 11191, 12408, 12825, 14078, 14531, 15892, 16381, 17850

Offset: 0

Robert Price, May 21 2016

Initialized with a single black (ON) cell at stage zero.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..128
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

Cf. A079317.

CAStep[rule_,a_]:=Map[rule[[10-#]]&,ListConvolve[{{0,2,0},{2,1,2},{0,2,0}},a,2],{2}];
code=678; stages=128;
rule=IntegerDigits[code,2,10];
g=2*stages+1; (* Maximum size of grid *)
a=PadLeft[{{1}},{g,g},0,Floor[{g,g}/2]]; (* Initial ON cell on grid *)
ca=a;
ca=Table[ca=CAStep[rule,ca],{n,1,stages+1}];
PrependTo[ca,a];
(* Trim full grid to reflect growth by one cell at each stage *)
k=(Length[ca[[1]]]+1)/2;
ca=Table[Table[Part[ca[[n]][[j]],Range[k+1-n,k-1+n]],{j,k+1-n,k-1+n}],{n,1,k}];
on=Map[Function[Apply[Plus,Flatten[#1]]],ca] (* Count ON cells at each stage *)
Table[Total[Part[on,Range[1,i]]],{i,1,Length[on]}] (* Sum at each stage *)

cp's OEIS Frontend

A079315 Number of cells that change from OFF to ON at stage n of the cellular automaton described in A079317.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A079316 Number of first-quadrant cells (including the two boundaries) that are ON at stage n of the cellular automaton described in A079317.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A151921 Net gain in number of ON cells at stage n of the cellular automaton described in A079317.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A079314 Number of first-quadrant cells (including the two boundaries) born at stage n of the Holladay-Ulam cellular automaton.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A079319 a(0) = 1; for n >= 1, a(n) = 4*a(n-1) - (2^n-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A079318 a(0) = 1; for n > 0, a(n) = (3^(A000120(n)-1) + 1)/2.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A151914 a(0)=0, a(1)=4; for n>=2, a(n) = (8/3)*(Sum_{i=1..n-1} 3^wt(i)) + 4, where wt() = A000120().

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A273409 Partial sums of the number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 678", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments