A072272 -id:A072272 - cp's OEIS frontend

A253908 Partial sums of A072272.

1, 6, 11, 28, 33, 58, 75, 136, 141, 166, 191, 276, 293, 378, 439, 656, 661, 686, 711, 796, 821, 946, 1031, 1336, 1353, 1438, 1523, 1812, 1873, 2178, 2395, 3168, 3173, 3198, 3223, 3308, 3333, 3458, 3543, 3848, 3873, 3998, 4123, 4548, 4633, 5058, 5363, 6448, 6465, 6550, 6635, 6924, 7009, 7434, 7723, 8760, 8821, 9126, 9431, 10468

Offset: 0

Omar E. Pol, Jan 27 2015

nonn

Also, total number of cubic ON cells after n generations in a three-dimensional cellular automaton where A072272(n) gives the number of cubic ON cells in the n-th level of the structure starting from the top. An ON cell remains ON forever. The structure looks like an irregular stepped pyramid.

N. J. A. Sloane, Table of n, a(n) for n = 0..8192
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A072272, A116520, A245542, A253767.

Offset changed to 0 by N. J. A. Sloane, Feb 06 2015

A170878 First differences of A072272.

Original entry on oeis.org

4, 0, 12, -12, 20, -8, 44, -56, 20, 0, 60, -68, 68, -24, 156, -212, 20, 0, 60, -60, 100, -40, 220, -288, 68, 0, 204, -228, 244, -88, 556, -768, 20, 0, 60, -60, 100, -40, 220, -280, 100, 0, 300, -340, 340, -120, 780, -1068, 68, 0, 204, -204, 340, -136, 748, -976, 244, 0, 732, -820, 868, -312, 1980, -2748

Offset: 0

N. J. A. Sloane, Jan 07 2010, Apr 17 2010

sign

David 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. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

A007483 a(n) = 3a(n-1) + 2a(n-2), with a(0)=1, a(1)=5.

Original entry on oeis.org

1, 5, 17, 61, 217, 773, 2753, 9805, 34921, 124373, 442961, 1577629, 5618809, 20011685, 71272673, 253841389, 904069513, 3219891317, 11467812977, 40843221565, 145465290649, 518082315077, 1845177526529, 6571697209741, 23405446682281, 83359734466325, 296890096763537

Offset: 0

N. J. A. Sloane, Sep 19 1994

Number of subsequences of [1,...,2n+1] in which each odd number has an even neighbor. The even neighbor must differ from the odd number by exactly 1.
From Gary W. Adamson, Aug 06 2016: (Start)
a(n) is the upper left term in the (n+1)-th matrix power of [(1,4); (1,2)] and is the INVERT transform of (1, 4, 4*2, 4*2^2, 4*2^3, 4*2^4, ...), i.e. of (1, 4, 8, 16, 32, 64, 128, ...).
The sequence is equal to row sums of an eigentriangle generated as follows: Let matrix A = an infinite lower triangle with (1, 4, 8, 16, ...) in every column and B = a triangle with (1, 1, 5, 17, 61, ...) as the rightmost diagonal and the rest zeros. Then the eigentriangle is A * B as follows: (1; 4, 1; 8, 4, 5; 16, 8, 20, 17; ...) with sums (1, 5, 17, 61, ...). Individual rows can be recovered by taking the dot product of (1, 4, 8, 16, ...) reversed and equal numbers of terms of(1, 1, 5, 17, ...). For example, 61 = (16, 8, 4, 1) dot (1, 1, 5, 17) = (16 + 8 + 20 + 17). (End)
The sequence is equal to A007482 convolved with (1, 2, 0, 0, 0, ...); i.e. (1 + 5x + 17x^2 + ...) = (1 + 3x + 11x^2 + 39x^3 + ...) * (1 + 2x). - Gary W. Adamson, Aug 08 2016
a(n) is the number of edge covers of the fan graph F(1,n+1) with a pendant attached to the vertex of degree n+1. - Feryal Alayont, Dec 08 2023

			a(2) = 17 = (8, 4, 1) dot (1, 1, 5) = 8 + 4 + 5. - _Gary W. Adamson_, Aug 06 2016
From _Feryal Alayont_, Dec 08 2023: (Start)
a(2) counts the edge covers of F(1,3) with a pendant attached at the vertex of degree 3. This is the graph:
      * -- *
    / | \
   /  |  \
  *---*---*
An edge cover is a subset of the edges where each vertex is an endpoint of at least one edge. We show a one-to-one correspondence between subsequences of [1,...,5] and edge covers. Label edges connecting the top left vertex to the bottom vertices with odd numbers, 1, 3, 5, left to right. Label bottom edges with 2 (left) and 4 (right). An odd number in the subsequence means that edge is not in the edge cover. An even number means that edge is in. All bottom vertices are covered because if an odd edge is missing, an even edge covers the vertex attached to that odd. The pendant edge must be in every cover, so that edge covers both top vertices. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..500
C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), Article 12.7.8.
A. Burstein, S. Kitaev, and T. Mansour, Independent sets in certain classes of (almost) regular graphs, arXiv:math/0310379 [math.CO], 2003.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
R. K. Guy and William O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly, 34, No. 2, 152-155 (1996). Math. Rev. 97d:11017.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Index entries for linear recurrences with constant coefficients, signature (3,2).

Cf. A007482, A072272, A122542.

a007483 n = a007483_list !! n
a007483_list = 1 : 5 : zipWith (+)
               (map (* 3) $ tail a007483_list) (map (* 2) a007483_list)
-- Reinhard Zumkeller, Nov 02 2015

[Floor((3/2+Sqrt(17)/2)^n*(1/2+7*Sqrt(17)/34)+(1/2-7*Sqrt(17)/34)*(3/2-Sqrt(17)/2)^n)+1: n in [0..30]]; // Vincenzo Librandi, Jul 09 2011

LinearRecurrence[{3, 2}, {1, 5}, 24] (* Jean-François Alcover, Sep 26 2017 *)
a[0]=1;a[1]=5;a[n_]:= a[n]= 3*a[n-1]+2*a[n-2];Table[a[n],{n,0,23}] (* James C. McMahon, Dec 17 2023 *)

a(n)=([1,2;2,2]^n*[1,2]~*[1,2])[1,1] \\ Charles R Greathouse IV, Jul 10 2011

@CachedFunction
def a(n): return 5^n if (n<2) else 3*a(n-1) + 2*a(n-2)
[a(n) for n in (0..40)] # G. C. Greubel, Jun 28 2021

G.f.: (1 + 2*x)/(1 - 3*x - 2*x^2).
a(n) = ((17 + 7*sqrt(17))/34)*((3 + sqrt(17))/2)^n* + ((17 - 7*sqrt(17))/34)*((3 - sqrt(17))/2)^n. - Paul Barry, Dec 08 2004
a(n-1) = Sum_{k=0..n} 2^(n-k)*A122542(n,k), n>=1. - Philippe Deléham, Oct 08 2006
a(n) = upper left term in the 2 X 2 matrix [1,2; 2,2]^(n+1). Also [a(n), a(n+1)] = the 2 X 2 matrix [0,1; 2,3]^(n+1) * [1,1]. Example: [0,1; 2,3]^4 * [1,1] = [61, 217]. - Gary W. Adamson, Mar 16 2008
Also, for n>=2, a(n)=[1,2;2,2]^(n-1)*[1,2]*[1,2]. - John M. Campbell, Jul 09 2011
a(n) = A007482(n) + 2*A007482(n-1). - R. J. Mathar, Sep 21 2012
a(n) = (i*sqrt(2))^(n-1)*( i*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) + 2*ChebyshevU(n-1, -3*i/(2*sqrt(2))) ). - G. C. Greubel, Jun 28 2021
E.g.f.: exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 7*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, May 24 2024

Definition simplified by N. J. A. Sloane, Aug 25 2014

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Aug 20 2014

nonn

This is the number of ON cells in a certain 2-D 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 odd-rule cellular automaton defined by OddRule 777 (see Ekhad-Sloane-Zeilberger "Odd-Rule 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).

			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(s-r)-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)

Alois P. Heinz, Table of n, a(n) for n = 0..8192
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule 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

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034.

Cf. A001045, A139818.

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 n-1 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);

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}] (* Jean-François Alcover, Apr 30 2017 *)

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

A246034 Number of odd terms in f^n, where f = x^4y^4 + x^4y^3 + x^3y^4 + x^4y^2 + x^2y^4 + x^4y + x^3y^2 + x^2y^3 + xy^4 + x^4 + x^2y^2 + y^4 + x^3 + x^2y + xy^2 + y^3 + x^2 + y^2 + x + y + 1.

Original entry on oeis.org

1, 21, 21, 85, 21, 233, 85, 321, 21, 441, 233, 761, 85, 1137, 321, 1545, 21, 441, 441, 1785, 233, 2925, 761, 3589, 85, 1785, 1137, 3977, 321, 4549, 1545, 5909, 21, 441, 441, 1785, 441, 4893, 1785, 6741, 233, 4893, 2925, 9949, 761, 11301, 3589, 13181, 85, 1785, 1785

Offset: 0

N. J. A. Sloane, Aug 20 2014

nonn

This is the number of ON cells in a certain 2-D 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.

			Here is the neighborhood:
[X, X, X, X, X]
[X, 0, X, 0, X]
[X, X, X, X, X]
[X, 0, X, 0, X]
[X, X, X, X, X]
which contains a(1) = 21 ON cells.

Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule 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

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246035.

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 n-1 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:=x^4*y^4+x^4*y^3+x^3*y^4+x^4*y^2+x^2*y^4+x^4*y+x^3*y^2+x^2*y^3+x*y^4+x^4+
   x^2*y^2+y^4+x^3+x^2*y+x*y^2+y^3+x^2+y^2+x+y+1;
OddCA(f, 100);

f = x^4*y^4 + x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^4*y + x^3*y^2 + x^2*y^3 + x*y^4 + x^4 + x^2*y^2 + y^4 + x^3 + x^2*y + x*y^2 + y^3 + x^2 + y^2 + x + y + 1;
a[0] = 1; a[n_] := Count[List @@ Expand[f^n] /. {x -> 1, y -> 1}, _?OddQ];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Dec 11 2017 *)

A255294 Number of 2's in expansion of F^n mod 3, where F = 1/x+2+x+1/y+y.

Original entry on oeis.org

0, 1, 5, 1, 8, 20, 5, 28, 64, 1, 8, 28, 8, 49, 101, 20, 109, 241, 5, 28, 80, 28, 149, 289, 64, 305, 437, 1, 8, 28, 8, 49, 109, 28, 149, 305, 8, 49, 149, 49, 272, 524, 101, 532, 1096, 20, 109, 305, 109, 572, 1096, 241, 1160

Offset: 0

N. J. A. Sloane, Feb 21 2015

nonn

A255293 and A255294 together are a second mod 3 analog of A072272.

			The pairs [no. of 1's, no. of 2's] are [1, 0], [4, 1], [8, 5], [4, 1], [17, 8], [29, 20], [8, 5], [37, 28], [49, 64], [4, 1], [17, 8], [37, 28], [17, 8], [76, 49], [128, 101], [29, 20], [136, 109], [196, 241], [8, 5], [37, 28], [89, 80], [37, 28], [176, 149], [292, 289], [49, 64], [260, 305], [584, 437], [4, 1], [17, 8], [37, 28], ...

Cf. A072272, A255287-A255294.

# C3 Counts 1's and 2's
C3 := proc(f) local c,ix,iy,f2,i,t1,t2,n1,n2;
f2:=expand(f) mod 3; n1:=0; n2:=0;
if whattype(f2) = `+` then
t1:=nops(f2);
for i from 1 to t1 do t2:=op(i, f2); ix:=degree(t2, x); iy:=degree(t2, y);
c:=coeff(coeff(t2,x,ix),y,iy);
if (c mod 3) = 1 then n1:=n1+1; else n2:=n2+1; fi; od: RETURN([n1,n2]);
else ix:=degree(f2, x); iy:=degree(f2, y);
c:=coeff(coeff(f2,x,ix),y,iy);
if (c mod 3) = 1 then n1:=n1+1; else n2:=n2+1; fi; RETURN([n1,n2]);
fi;
end;
F4:=1/x+2+x+1/y+y mod 3;
g:=(F,n)->expand(F^n) mod 3;
[seq(C3(g(F4,n))[2],n=0..60)];

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

Original entry on oeis.org

1, 4, 4, 12, 4, 16, 12, 40, 4, 16, 16, 48, 12, 48, 40, 128, 4, 16, 16, 48, 16, 64, 48, 160, 12, 48, 48, 144, 40, 160, 128, 416, 4, 16, 16, 48, 16, 64, 48, 160, 16, 64, 64, 192, 48, 192, 160, 512, 12, 48, 48, 144, 48, 192, 144, 480, 40, 160, 160, 480, 128, 512, 416

Offset: 0

N. J. A. Sloane, Jan 26 2015

nonn

This is the number of ON cells in a certain 2-D 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 odd-rule cellular automaton defined by OddRule 017 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015

			Here is the neighborhood f:
[0, X, 0]
[X, X, X]
which contains a(1) = 4 ON cells.

Alois P. Heinz, Table of n, a(n) for n = 0..8191
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796, 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249, 2015.
Po-Yi Huang and Wen-Fong Ke, Sequences Derived from The Symmetric Powers of {1,2,...,k}, arXiv:2307.07733 [math.CO], 2023.
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, 2015
Index entries for sequences related to cellular automata

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034, A246035.

Cf. A087206.

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 n-1 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+y;
OddCA(f, 130);

f[n_] := 2^n*Fibonacci[n+2]; Table[Times @@ (f[Length[#]]&) /@ Select[ Split[ IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 62}] (* Jean-François Alcover, Jul 11 2017 *)

This is the Run Length Transform of A087206.

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

Original entry on oeis.org

1, 5, 5, 17, 5, 25, 17, 65, 5, 25, 25, 85, 17, 85, 65, 229, 5, 25, 25, 85, 25, 125, 85, 325, 17, 85, 85, 289, 65, 325, 229, 813, 5, 25, 25, 85, 25, 125, 85, 325, 25, 125, 125, 425, 85, 425, 325, 1145, 17, 85, 85, 289, 85, 425, 289, 1105, 65, 325, 325, 1105, 229, 1145, 813, 2945, 5, 25, 25, 85

Offset: 0

N. J. A. Sloane, Jan 26 2015

nonn

This is the number of ON cells in a certain 2-D 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 odd-rule cellular automaton defined by OddRule 171 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link).

			Here is the neighborhood f:
[0, 0, X]
[X, X, X]
[0, 0, X]
which contains a(1) = 5 ON cells.

Alois P. Heinz, Table of n, a(n) for n = 0..8191
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule 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

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034, A246035, A253064, A253066.

Cf. A253067.

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 n-1 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+x^2+x^2*y+x^2/y;
OddCA(f, 130);

(* f = A253067 *) f[0]=1; f[1]=5; f[2]=17; f[3]=65; f[4]=229; f[5]=813; f[n_] := f[n] = 8 f[n-5] + 6 f[n-4] + 13 f[n-3] + 5 f[n-2] + f[n-1]; Table[Times @@ (f[Length[#]]&) /@ Select[s = Split[IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 67}] (* Jean-François Alcover, Jul 12 2017 *)

This is the Run Length Transform of A253067.

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

Original entry on oeis.org

1, 6, 6, 28, 6, 36, 28, 112, 6, 36, 36, 168, 28, 168, 112, 456, 6, 36, 36, 168, 36, 216, 168, 672, 28, 168, 168, 784, 112, 672, 456, 1816, 6, 36, 36, 168, 36, 216, 168, 672, 36, 216, 216, 1008, 168, 1008, 672, 2736, 28, 168, 168, 784, 168, 1008, 784, 3136, 112, 672, 672, 3136, 456, 2736, 1816, 7288

Offset: 0

N. J. A. Sloane, Jan 29 2015

nonn

This is the number of ON cells in a certain 2-D 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 odd-rule cellular automaton defined by OddRule 275 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link).

			Here is the neighborhood f:
[X, 0, X]
[X, X, X]
[0, X, 0]
which contains a(1) = 6 ON cells.

Alois P. Heinz, Table of n, a(n) for n = 0..8191
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule 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

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034, A246035, A253064, A253065.

Cf. A253068.

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 n-1 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+y/x+x*y;
OddCA(f, 130);

(* f = A253068 *) f[0] = 1; f[n_] := ((-2)^n + 4^(n+2)-8)/9; Table[Times @@ (f[Length[#]]&) /@ Select[s = Split[IntegerDigits[n, 2]], #[[1]] == 1 &], {n, 0, 63}] (* Jean-François Alcover, Jul 12 2017 *)

This is the Run Length Transform of A253068.

A164982 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

Original entry on oeis.org

1, 3, 4, 12, 7, 21, 16, 40, 22, 42, 34, 67, 52, 85, 70, 125, 94, 126, 102, 150, 118, 172, 177, 234, 209, 240, 238, 319, 285, 363, 378, 458, 383, 444, 404, 493, 474, 520, 529, 628, 583, 602, 622, 727, 664, 816, 835, 948, 873, 926, 952, 1065, 1010, 1090, 1187

Offset: 1

John W. Layman, Sep 03 2009

nonn

The cells are the squares of the standard square grid. All cells are initially OFF and one cell is turned ON at generation 1. At subsequent generations a cell is ON if and only if (1) exactly one of neighbors NW, NE, and S was ON, or (2) all three of cells N, SW, and SE were ON in the previous generation. (The 9-cell Moore neighborhood is labeled {{NW,N,NE},{W,C,E},{SW,S,SE}}).

John W. Layman, Graphs of the automaton for generations 1-20 [From _John W. Layman_, Sep 14 2009]
Index entries for sequences related to cellular automata

Cf. A048883, A072272, A122108, A160410, A247002.

RasterGraphics[state_?MatrixQ, colors_Integer : 2, opts___] := Graphics[Raster[Reverse[1 - state/(colors - 1)]], AspectRatio -> (AspectRatio /. {opts} /. AspectRatio -> Automatic), Frame -> True, FrameTicks -> None, GridLines -> None];
rule=61986;
Show[GraphicsArray[Map[RasterGraphics, CellularAutomaton[{rule, {2, {{1, 4, 1}, {0, 0, 0}, {4, 1, 4}}}, {1, 1}}, {{{1}}, 0}, 4, -5]]]];
ca = CellularAutomaton[{rule, {2, {{1, 4, 1}, {0, 0, 0}, {4, 1, 4}}}, {1, 1}}, {{{1}}, 0}, 99, -100];
Table[Total[ca[[i]], 2], {i, 1, 100}]

cp's OEIS Frontend

A253908 Partial sums of A072272.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A170878 First differences of A072272.

Views

Author

Keywords

Links

A007483 a(n) = 3*a(n-1) + 2*a(n-2), with a(0)=1, a(1)=5.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246034 Number of odd terms in f^n, where f = x^4*y^4 + x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^4*y + x^3*y^2 + x^2*y^3 + x*y^4 + x^4 + x^2*y^2 + y^4 + x^3 + x^2*y + x*y^2 + y^3 + x^2 + y^2 + x + y + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A255294 Number of 2's in expansion of F^n mod 3, where F = 1/x+2+x+1/y+y.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

A007483 a(n) = 3a(n-1) + 2a(n-2), with a(0)=1, a(1)=5.

A246034 Number of odd terms in f^n, where f = x^4y^4 + x^4y^3 + x^3y^4 + x^4y^2 + x^2y^4 + x^4y + x^3y^2 + x^2y^3 + xy^4 + x^4 + x^2y^2 + y^4 + x^3 + x^2y + xy^2 + y^3 + x^2 + y^2 + x + y + 1.