The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A267190 Number of ON cells after n generations of the cellular automaton on the square grid that is described in the Comments. 5
0, 1, 5, 9, 13, 25, 29, 41, 53, 65, 85, 97, 117, 145, 149, 161, 173, 193, 221, 241, 277, 313, 357, 401, 437, 489, 541, 553, 581, 609, 645, 689, 733, 801, 869, 945, 1021, 1081, 1149, 1217, 1277, 1345, 1397, 1433, 1501, 1569, 1653, 1753, 1829, 1905, 1997, 2057, 2141, 2225, 2317, 2449, 2549, 2681, 2797, 2889, 2965, 3041, 3149, 3289 (list; graph; refs; listen; history; text; internal format)



The cells are the squares of the standard square grid.

Cells are either OFF or ON, once they are ON they stay ON, and we begin in generation 1 with 1 ON cell.

Each cell has 4 neighbors, those that it shares an edge with. Cells that are ON at generation n all try simultaneously to turn ON all their neighbors that are OFF. They can only do this at this point in time; afterwards they go to sleep (but stay ON).

A square Q is turned ON at generation n+1 if:

a) Q shares an edge with one and only one square P (say) that was turned ON at generation n (in which case the two squares which intersect Q only in a vertex not on that edge are called Q's “outer squares”), and

b) Q's outer squares were not turned ON in any previous generation, and

c) Q's outer squares are not prospective squares of the (n+1)st generation satisfying a).

A151895, A151906, and A170896 are closely related cellular automata.

The key difference between this and A170896 is that if we have two squares Q1 and Q2, both satisfying a), and that are each an outer square of the other, where Q1 satisfies b), but Q2 does not, then for A170896 Q1 is accepted, but for this sequence Q1 is eliminated.  This first happens at n=14, when, for example, A170896 turns (8,3) ON but A267190 doesn't (because (9,2) fails to satisfy b) because (8,1) is ON). - David Applegate, Jan 30 2016

A151895 and A267190 first differ at n=17, when A267190 turns (12,2) ON even though its outer square (11,1) was considered (not turned ON) in a previous generation. - David Applegate, Jan 30 2016


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


David Applegate, Table of n, a(n) for n = 0..260

David Applegate, The movie version

David Applegate, After 16 generations, illustrating a(16)=173 (with the A267191(16)=12 newly created cells shown in blue)

David Applegate, After 36 generations, illustrating a(36)=1021 (with the A267191(36)=76 newly created cells shown in blue) 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

S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215-224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962 [Annotated scanned copy]

Index entries for sequences related to toothpick sequences

Index entries for sequences related to cellular automata


We do not know of a recurrence or generating function.


Cf. A267191 (first differences), A151895, A151906, A170896.

See also A139250.

Sequence in context: A271391 A151907 A151895 * A170896 A323106 A257171

Adjacent sequences:  A267187 A267188 A267189 * A267191 A267192 A267193




David Applegate and N. J. A. Sloane, Jan 21 2016


Corrected by David Applegate, Jan 30 2016



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 23:25 EDT 2021. Contains 346273 sequences. (Running on oeis4.)