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

 

Logo


Hints
(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

%I

%S 0,1,5,9,13,25,29,41,53,65,85,97,117,145,157,169,181,201,229,249,285,

%T 321,365,409,445,497,549,577,605,633,669,713,757,825,893,969,1045,

%U 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

%N Number of ON cells after n generations of the Schrandt-Ulam cellular automaton on the square grid that is described in the Comments.

%C The cells are the squares of the standard square grid.

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

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

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

%C 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

%C b) Q's outer squares were not turned ON in any previous generation.

%C 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.

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

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

%H David Applegate, <a href="/A170896/b170896.txt">Table of n, a(n) for n = 0..260</a> (corrected by Sean A. Irvine)

%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>

%H David Applegate, <a href="/A170896/a170896.pdf">After 20 generations, illustrating a(20)=285 (with the A170897(20)=36 newly created cells shown in blue)</a>

%H David Applegate, <a href="/A170896/a170896_1.pdf">After 26 generations, illustrating a(26)=549 (with the A170897(26)=52 newly created cells shown in blue)</a>

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, 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.]

%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a170/A170896.java">Java program</a> (github)

%H R. G. Schrandt and S. M. Ulam, <a href="http://library.lanl.gov/cgi-bin/getfile?00359037.pdf">On recursively defined geometric objects and patterns of growth</a> [Link supplied by Laurinda J. Alcorn, Jan 09 2010.]

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=9ogbsh8KuEM">Exciting Number Sequences</a> (video of talk), Mar 05 2021

%H S. M. Ulam, <a href="/A002858/a002858.pdf">On some mathematical problems connected with patterns of growth of figures</a>, 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]

%F We do not know of a recurrence or generating function.

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

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Jan 09 2010

%E 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 July 29 07:28 EDT 2021. Contains 346340 sequences. (Running on oeis4.)