login
Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.
26

%I #153 Feb 24 2021 02:48:19

%S 1,5,9,21,25,37,57,85,89,101,121,149,169,213,281,341,345,357,377,405,

%T 425,469,537,597,617,661,729,805,889,1045,1241,1365,1369,1381,1401,

%U 1429,1449,1493,1561,1621,1641,1685,1753,1829,1913,2069,2265,2389,2409,2453,2521

%N Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.

%C Square grid, 4 neighbors per cell (N, E, S, W cells), turn ON iff exactly 1 or 3 neighbors are ON; once ON, cells stay ON.

%C The terms agree with those of A246335 for n <= 11, although the configurations are different starting at n = 7. - _N. J. A. Sloane_, Sep 21 2014

%C Offset 1 is best for giving a formula for a(n), although the Maple and Mathematica programs index the states starting at state 0.

%C It appears that this shares infinitely many terms with both A162795 and A147562, see Formula section and Example section. - _Omar E. Pol_, Feb 19 2015

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

%H N. J. A. Sloane and Vincenzo Librandi, <a href="/A169707/b169707.txt">Table of n, a(n) for n = 1..513</a>, computed from the definition, not using the conjectured formula. [The first 200 terms were found by _Vincenzo Librandi_]

%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</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.], <a href="http://arxiv.org/abs/1004.3036">arXiv:1004.3036 [math.CO]</a>.

%H N. J. A. Sloane, <a href="/A169707/a169707_1.txt">Table of n, a(n) for n=1..8192 assuming the recurrence is correct.</a> Note that these terms are merely conjectures.

%H N. J. A. Sloane, <a href="/A169707/a169707.pdf">Illustration of first 24 generations</a>

%H N. J. A. Sloane, <a href="/A169707/a169707_1.png">Illustration of first 24 generations of the NW-NE-SE-SW version of this CA</a>

%H N. J. A. Sloane, <a href="/A169707/a169707_2.png">Illustration of generation 7 of the NW-NE-SE-SW version of this CA</a> (containing a(7) = 57 ON cells)

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.

%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 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F a(2^k + i) = (4^(k+1)-1)/3 + 4*A246336(i), for k >= 0, 0 <= i < 2^k. For example, if n = 15 = 2^3 + 7, so k=3, i=7, we have a(15) = (4^4-1)/3 + 4*A246336(7) = 85 + 4*49 = 281.

%F a(n) = 1 + 2*(A139250(n) - A160552(n)) = A160164(n) - A170903(n) = A187220(n) + 2*(A160552(n-1)). - _Omar E. Pol_, Feb 18 2015

%F It appears that a(n) = A162795(n) = A147562(n), if n is a member of A048645, otherwise a(n) > A162795(n) > A147562(n). - _Omar E. Pol_, Feb 19 2015

%F It appears that a(n) = 1 + 4*A255747(n-1). - _Omar E. Pol_, Mar 05 2015

%F It appears that a(n) = 1 + 4*(A139250(n-1) - (a(n-1) - 1)/4), n > 1. - _Omar E. Pol_, Jul 24 2015

%F It appears that a(2n) = 1 + 4*A162795(n). - _Omar E. Pol_, Jul 04 2017

%e Divides naturally into blocks of sizes 1,2,4,8,16,...:

%e 1,

%e 5, 9,

%e 21, 25, 37, 57,

%e 85, 89, 101, 121, 149, 169, 213, 281, <- terms 8 through 15

%e 341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241,

%e 1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521, ...

%e From _Omar E. Pol_, Feb 18 2015: (Start)

%e Also, written as an irregular triangle T(j,k), k>=1, in which the row lengths are the terms of A011782:

%e 1;

%e 5;

%e 9, 21;

%e 25, 37, 57, 85;

%e 89, 101, 121, 149, 169, 213, 281, 341;

%e 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365;

%e The right border gives the positive terms of A002450.

%e It appears that T(j,k) = A162795(j,k) = A147562(j,k), if k is a power of 2, for example: it appears that the three mentioned triangles only share the elements from the columns 1, 2, 4, 8, 16, ...

%e (End)

%p (Maple program that uses the actual definition of the automaton, rather than the (conjectured) formula, from _N. J. A. Sloane_, Feb 15 2015):

%p # Count terms in a polynomial:

%p C := f->`if`(type(f, `+`), nops(f), 1);

%p # Replace all nonzero coeffts by 1:

%p bool := proc(f) local ix, iy, f2, i, t1, t2, A;

%p f2:=expand(f);

%p if whattype(f) = `+` then

%p t1:=nops(f2); A:=0;

%p for i from 1 to t1 do t2:=op(i, f2); ix:=degree(t2, x); iy:=degree(t2, y);

%p A:=A+x^ix*y^iy; od: A;

%p else ix:=degree(f2, x); iy:=degree(f2, y); x^ix*y^iy;

%p fi;

%p end;

%p # a loop that produces M steps of A169707 and A169708:

%p M:=20;

%p F:=x*y+x/y+1/x*y+1/x/y mod 2;

%p GG[0]:=1;

%p for n from 1 to M do dd[n]:=expand(F*GG[n-1]) mod 2;

%p GG[n]:=bool(GG[n-1]+dd[n]);

%p lprint(n,C(GG[n]), C(GG[n]-GG[n-1])); od:

%t Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 750, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]]

%t ArrayPlot /@ CellularAutomaton[{750, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 23]

%t (* The next two lines deal with the equivalent CA based on neighbors NW, NE, SE, SW. This is to facilitate the comparison with A246333 and A246335 *)

%t Map[Function[Apply[Plus, Flatten[ #1]]], CellularAutomaton[{ 750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 100]]

%t ArrayPlot /@ CellularAutomaton[{750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 23]

%Y Cf. A169708 (first differences), A147562, A147582, A169648, A169649, A169709, A169710, A246333, A246334, A246335, A246336, A253098 (partial sums).

%Y Cf. also A162795, A150552, A160104, A170903, A048645, A187200.

%Y See A253088 for the analogous CA using Rule 750 and a 9-celled neighborhood.

%K nonn,look

%O 1,2

%A _N. J. A. Sloane_, Apr 17 2010

%E Edited (added formula, illustration, etc.) by _N. J. A. Sloane_, Aug 30 2014

%E Offset changed to 1 by _N. J. A. Sloane_, Feb 09 2015