A151895 - OEIS

%I #21 Oct 10 2022 09:38:12

%S 0,1,5,9,13,25,29,41,53,65,85,97,117,145,149,161,173,185,213,233,261,

%T 297,333,385,429,481,533,545,573,601,629,673,717,761,837,905,989,1033,

%U 1085,1145,1197,1257,1309,1337,1397,1457,1525,1625,1669

%N Number of ON cells after n generations of the 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 considered (that is, satisfied a)) in any previous generation, and

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

%C Originally constructed in an attempt to explain the Holladay-Ulam CA shown in Fig. 2 of the 1962 Ulam article. However, as explained on page 222 of that article, the actual rule for that CA (see A151906, A151907) is different from ours.

%C A170896 and A267190 are also closely related cellular automata.

%C 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 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="/A151895/b151895.txt">Table of n, a(n) for n = 0..250</a>

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

%H David Applegate, <a href="/A151895/a151895_10.pdf">Illustration of first 10 generations</a>

%H David Applegate, <a href="/A151895/a151895_20.pdf">Illustration of first 20 generations</a>

%H David Applegate, <a href="/A151895/a151895_32.pdf">Illustration of first 32 generations</a>

%H David Applegate, <a href="/A151895/a151895_64.pdf">Illustration of first 64 generations</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.], which is also available at <a href="http://arxiv.org/abs/1004.3036">arXiv:1004.3036v2</a>

%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="/A151895/a151895.jpg">Illustration of initial terms</a> (concentrating on a 90-degree sector)

%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 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 See A170896, A170897 for the original Schrandt-Ulam version.

%Y Cf. A151896 (the first differences), A139250, A151905, A151906, A151907, A267190, A267191.

%K nonn

%O 0,3

%A _David Applegate_ and _N. J. A. Sloane_, Jul 30 2009

%E Entry (including definition) revised by _David Applegate_ and _N. J. A. Sloane_, Jan 21 2016