A079315 -id:A079315 - cp's OEIS frontend

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

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

A079317 Number of ON cells after n generations of cellular automaton on square grid in which cells which share exactly one edge with an ON cell change their state.

Original entry on oeis.org

1, 5, 5, 17, 9, 29, 21, 65, 25, 77, 37, 113, 49, 149, 85, 257, 89, 269, 101, 305, 113, 341, 149, 449, 161, 485, 197, 593, 233, 701, 341, 1025, 345, 1037, 357, 1073, 369, 1109, 405, 1217, 417, 1253, 453, 1361, 489, 1469, 597, 1793, 609, 1829, 645, 1937, 681

Offset: 0

N. J. A. Sloane, Feb 12 2003

We work on the square grid in which each cell has four neighbors.
Start with cell (0,0) ON and all other cells OFF; at each succeeding stage the cells that share exactly one edge with an ON 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
If cells never turn OFF we get the CA of A147562.
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. - Robert Price, May 21 2016

			Generations 1 through 4 (X = ON):
..................X
..........X......XXX
....X...........X...X
X..XXX..X.X.X..XX.X.XX
....X...........X...X
..........X......XXX
..................X
...........Sizes of first 20 generations:.........
.........n...OFF->ON...ON->OFF..Net gain..Total ON
.........n...A079315.(A147582)...A151921...A079317
--------------------------------------------------
.........0.........0.........0.........0.........0
.........1.........1.........0.........1.........1
.........2.........4.........0.........4.........5
.........3.........4.........4.........0.........5
.........4........12.........0........12........17
.........5.........4........12........-8.........9
.........6........20.........0........20........29
.........7........12........20........-8........21
.........8........44.........0........44........65
.........9.........4........44.......-40........25
........10........52.........0........52........77
........11........12........52.......-40........37
........12........76.........0........76.......113
........13........12........76.......-64........49
........14.......100.........0.......100.......149
........15........36.......100.......-64........85
........16.......172.........0.......172.......257
........17.........4.......172......-168........89
........18.......180.........0.......180.......269
........19........12.......180......-168.......101
........20.......204.........0.......204.......305

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..128
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.]
Robert Price, Diagrams of the first 20 stages
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 [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. A079315 gives number which change from OFF to ON at generation n, A151921 gives net gain in number of ON cells.

a(n) = a(n-1) + A151921(n) (and we have an explicit formula for A151921).

More terms from John W. Layman, Oct 29 2003

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

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

Original entry on oeis.org

0, 1, 3, 5, 11, 13, 19, 25, 43, 45, 51, 57, 75, 81, 99, 117, 171, 173, 179, 185, 203, 209, 227, 245, 299, 305, 323, 341, 395, 413, 467, 521, 683, 685, 691, 697, 715, 721, 739, 757, 811, 817, 835, 853, 907, 925, 979, 1033, 1195, 1201, 1219

Offset: 0

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

Also, total number of "ON" cells 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. It appears that this is very close to A139250, the toothpick sequence. - Omar E. Pol, Feb 22 2015

			n=3: (2/3)*(3^1+3^1+3^2+3^1) + 1 = (2/3)*18 + 1 = 13.

Michel Marcus, Table of n, a(n) for n = 0..10000
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. 31.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A000120, A007583, A139250, A147562, A151914, A151920.

Array[(2/3) Sum[3^(Total@ IntegerDigits[i, 2]), {i, # - 1}] + 1 &, 50] (* Michael De Vlieger, Nov 01 2022 *)

a(n) = if (n<2, n, 1 + 2*sum(i=1,n-1, 3^hammingweight(i))/3); \\ Michel Marcus, Feb 22 2015

a(n) = A151914(n)/4.
a(n) = A079315(2n)/4.
For n>=2, a(n) = 2*A151920(n-2) + 1.
For n>=1, a(n) = (1 + A147562(n))/2. - Omar E. Pol, Mar 13 2011
a(2^k) = A007583(k), if k >= 0. - Omar E. Pol, Feb 22 2015

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

A151885 Similar to the original toothpick sequence A139250, except that the rule is now: a toothpick changes state if its midpoint is adjacent to exactly one ON toothpick.

Original entry on oeis.org

0, 1, 3, 5, 11, 5, 15, 17, 39, 5, 15, 25, 55, 17, 51, 61, 139, 5, 15, 25, 55, 25, 75, 85, 195, 17, 51, 85, 187, 61, 183, 217, 495, 5, 15, 25, 55, 25, 75, 85, 195, 25, 75, 125, 275, 85, 255, 305, 695, 17, 51, 85, 187, 85, 255, 289, 663

Offset: 0

N. J. A. Sloane, Jul 23 2009

nonn

In the original toothpick sequence A139250, a toothpick simply turned ON (and stayed ON) if its midpoint was adjacent to exactly one ON toothpick.

Related to A139250 in the same way that A079315 is related to A147562.

Nathaniel Johnston, Table of n, a(n) for n = 0..925
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.]
Nathaniel Johnston, C program for computing terms of A151885-A151888
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane, Illustration of first 8 generations

Cf. A151886-A151888, A139250, A139251, A147562, A079314, A079315.

a(n) = a(n-1) + A151888(n).

Terms after a(8) from Nathaniel Johnston, Apr 02 2011

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

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.

A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton.

Original entry on oeis.org

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

Offset: 1

John W. Layman, Aug 08 2009

nonn

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.

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

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

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

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

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

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)

cp's OEIS Frontend

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

A079317 Number of ON cells after n generations of cellular automaton on square grid in which cells which share exactly one edge with an ON cell change their state.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A151885 Similar to the original toothpick sequence A139250, except that the rule is now: a toothpick changes state if its midpoint is adjacent to exactly one ON toothpick.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

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

Views

Author

Keywords