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!)
A170896 Number of ON cells after n generations of the Schrandt-Ulam cellular automaton on the square grid that is described in the Comments. 9
0, 1, 5, 9, 13, 25, 29, 41, 53, 65, 85, 97, 117, 145, 157, 169, 181, 201, 229, 249, 285, 321, 365, 409, 445, 497, 549, 577, 605, 633, 669, 713, 757, 825, 893, 969, 1045, 1105, 1173, 1241, 1309, 1377, 1437, 1473, 1541, 1609, 1693, 1793, 1869, 1945, 2037, 2105, 2189, 2281, 2381, 2521, 2621, 2753, 2869, 2969, 3053, 3129, 3237, 3377, 3485, 3585, 3685, 3817, 3909 (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.

c) In addition, of this set of prospective squares of the (n+1)th generation satisfying the previous condition, we eliminate all squares which are outer squares of other prospective squares.

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


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 (corrected by Sean A. Irvine)

David Applegate, The movie version

David Applegate, After 20 generations, illustrating a(20)=285 (with the A170897(20)=36 newly created cells shown in blue)

David Applegate, After 26 generations, illustrating a(26)=549 (with the A170897(26)=52 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.]

Sean A. Irvine, Java program (github)

R. G. Schrandt and S. M. Ulam, On recursively defined geometric objects and patterns of growth [Link supplied by Laurinda J. Alcorn, Jan 09 2010.]

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021

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]


We do not know of a recurrence or generating function.


Cf. A139250, A170897 (first differences), A151895, A151896, A151906, A267190.

Sequence in context: A151907 A151895 A267190 * A323106 A257171 A233973

Adjacent sequences:  A170893 A170894 A170895 * A170897 A170898 A170899




N. J. A. Sloane, Jan 09 2010


Entry (including definition) revised by David Applegate and N. J. A. Sloane, Jan 21 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 June 18 07:25 EDT 2021. Contains 345098 sequences. (Running on oeis4.)