

A246035


Number of odd terms in f^n, where f = (1/x+1+x)*(1/y+1+y).


13



1, 9, 9, 25, 9, 81, 25, 121, 9, 81, 81, 225, 25, 225, 121, 441, 9, 81, 81, 225, 81, 729, 225, 1089, 25, 225, 225, 625, 121, 1089, 441, 1849, 9, 81, 81, 225, 81, 729, 225, 1089, 81, 729, 729, 2025, 225, 2025, 1089, 3969, 25, 225, 225, 625, 225, 2025, 625, 3025, 121, 1089, 1089, 3025, 441, 3969, 1849, 7225, 9, 81, 81, 225, 81, 729, 225
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

This is the number of ON cells in a certain 2D CA in which the neighborhood of a cell is defined by f, and in which a cell is ON iff there was an odd number of ON cells in the neighborhood at the previous generation.
This is the oddrule cellular automaton defined by OddRule 777 (see EkhadSloaneZeilberger "OddRule Cellular Automata on the Square Grid" link).
Run Length Transform of {A001045(k+2)^2} (or of A139818).
The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g. 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product).


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..8192
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A MetaAlgorithm for Creating Fast Algorithms for Counting ON Cells in OddRule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, OddRule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Index entries for sequences related to cellular automata


FORMULA

a(n) = A071053(n)^2.


EXAMPLE

Here is the neighborhood:
[X, X, X]
[X, X, X]
[X, X, X]
which contains a(1) = 9 ON cells.
.
From Omar E. Pol, Mar 17 2015: (Start)
Apart from the initial 1, the sequence can be written also as an irregular tetrahedron T(s,r,k) = A139818(r+2) * a(k), s>=1, 1<=r<=s, 0<=k<=(A011782(sr)1) as shown below:
..
9;
...
9;
25;
..........
9, 81;
25;
121;
....................
9, 81, 81, 225;
25, 225;
121;
441;
........................................
9, 81, 81, 225, 81, 729, 225, 1089;
25, 225, 225, 625;
121, 1089;
441;
1849;
...
Note that every row r is equal to A139818(r+2) times the beginning of the sequence itself, thus in 3D every column contains the same number: T(s,r,k) = T(s+1,r,k).
(End)


MAPLE

C:=f>subs({x=1, y=1}, f);
# Find number of ON cells in CA for generations 0 thru M defined by rule
# that cell is ON iff number of ON cells in nbd at time n1 was odd
# where nbd is defined by a polynomial or Laurent series f(x, y).
OddCA:=proc(f, M) global C; local n, a, i, f2, p;
f2:=simplify(expand(f)) mod 2;
a:=[]; p:=1;
for n from 0 to M do a:=[op(a), C(p)]; p:=expand(p*f2) mod 2; od:
lprint([seq(a[i], i=1..nops(a))]);
end;
f:=(1/x+1+x)*(1/y+1+y);
OddCA(f, 70);


MATHEMATICA

b[0] = 1; b[n_] := b[n] = Expand[b[n  1]*(x^2 + x + 1)];
a[n_] := Count[CoefficientList[b[n], x], _?OddQ]^2;
Table[a[n], {n, 0, 100}] (* JeanFrançois Alcover, Apr 30 2017 *)


CROSSREFS

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034.
Cf. A001045, A139818.
Sequence in context: A144424 A282269 A205380 * A147340 A147499 A146591
Adjacent sequences: A246032 A246033 A246034 * A246036 A246037 A246038


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Aug 20 2014


STATUS

approved



