cp's OEIS Frontend

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

%I A169707 #153 Feb 24 2021 02:48:19
%S A169707 1,5,9,21,25,37,57,85,89,101,121,149,169,213,281,341,345,357,377,405,
%T A169707 425,469,537,597,617,661,729,805,889,1045,1241,1365,1369,1381,1401,
%U A169707 1429,1449,1493,1561,1621,1641,1685,1753,1829,1913,2069,2265,2389,2409,2453,2521
%N A169707 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.
%C A169707 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 A169707 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 A169707 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 A169707 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 A169707 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.
%H A169707 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 A169707 David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>
%H A169707 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 A169707 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 A169707 N. J. A. Sloane, <a href="/A169707/a169707.pdf">Illustration of first 24 generations</a>
%H A169707 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 A169707 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 A169707 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 A169707 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 A169707 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A169707 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 A169707 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 A169707 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 A169707 It appears that a(n) = 1 + 4*A255747(n-1). - _Omar E. Pol_, Mar 05 2015
%F A169707 It appears that a(n) = 1 + 4*(A139250(n-1) - (a(n-1) - 1)/4), n > 1. - _Omar E. Pol_, Jul 24 2015
%F A169707 It appears that a(2n) = 1 + 4*A162795(n). - _Omar E. Pol_, Jul 04 2017
%e A169707 Divides naturally into blocks of sizes 1,2,4,8,16,...:
%e A169707 1,
%e A169707 5, 9,
%e A169707 21, 25, 37, 57,
%e A169707 85, 89, 101, 121, 149, 169, 213, 281, <- terms 8 through 15
%e A169707 341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241,
%e A169707 1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521, ...
%e A169707 From _Omar E. Pol_, Feb 18 2015: (Start)
%e A169707 Also, written as an irregular triangle T(j,k), k>=1, in which the row lengths are the terms of A011782:
%e A169707 1;
%e A169707 5;
%e A169707 9,   21;
%e A169707 25,  37,   57,  85;
%e A169707 89,  101, 121, 149, 169, 213, 281, 341;
%e A169707 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365;
%e A169707 The right border gives the positive terms of A002450.
%e A169707 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 A169707 (End)
%p A169707 (Maple program that uses the actual definition of the automaton, rather than the (conjectured) formula, from _N. J. A. Sloane_, Feb 15 2015):
%p A169707 # Count terms in a polynomial:
%p A169707 C := f->`if`(type(f, `+`), nops(f), 1);
%p A169707 # Replace all nonzero coeffts by 1:
%p A169707 bool := proc(f) local ix, iy, f2, i, t1, t2, A;
%p A169707 f2:=expand(f);
%p A169707 if whattype(f) = `+` then
%p A169707 t1:=nops(f2); A:=0;
%p A169707 for i from 1 to t1 do t2:=op(i, f2); ix:=degree(t2, x); iy:=degree(t2, y);
%p A169707 A:=A+x^ix*y^iy; od: A;
%p A169707 else ix:=degree(f2, x); iy:=degree(f2, y); x^ix*y^iy;
%p A169707 fi;
%p A169707 end;
%p A169707 # a loop that produces M steps of A169707 and A169708:
%p A169707 M:=20;
%p A169707 F:=x*y+x/y+1/x*y+1/x/y mod 2;
%p A169707 GG[0]:=1;
%p A169707 for n from 1 to M do dd[n]:=expand(F*GG[n-1]) mod 2;
%p A169707 GG[n]:=bool(GG[n-1]+dd[n]);
%p A169707 lprint(n,C(GG[n]), C(GG[n]-GG[n-1])); od:
%t A169707 Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 750, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]]
%t A169707 ArrayPlot /@ CellularAutomaton[{750, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 23]
%t A169707 (* 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 A169707 Map[Function[Apply[Plus, Flatten[ #1]]], CellularAutomaton[{ 750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 100]]
%t A169707 ArrayPlot /@ CellularAutomaton[{750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 23]
%Y A169707 Cf. A169708 (first differences), A147562, A147582, A169648, A169649, A169709, A169710, A246333, A246334, A246335, A246336, A253098 (partial sums).
%Y A169707 Cf. also A162795, A150552, A160104, A170903, A048645, A187200.
%Y A169707 See A253088 for the analogous CA using Rule 750 and a 9-celled neighborhood.
%K A169707 nonn,look
%O A169707 1,2
%A A169707 _N. J. A. Sloane_, Apr 17 2010
%E A169707 Edited (added formula, illustration, etc.) by _N. J. A. Sloane_, Aug 30 2014
%E A169707 Offset changed to 1 by _N. J. A. Sloane_, Feb 09 2015