A246035 -id:A246035 - cp's OEIS frontend

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

1, 3, 3, 5, 3, 9, 5, 11, 3, 9, 9, 15, 5, 15, 11, 21, 3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27

Offset: 0

Hans Havermann, May 26 2002

Number of 1's in n-th row of triangle in A071036.
Number of odd coefficients in (x^2+x+1)^n. - Benoit Cloitre, Sep 05 2003. This result was given in Wolfram (1983). - N. J. A. Sloane, Feb 17 2015
This is also the odd-rule cellular automaton defined by OddRule 007 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
This is the Run Length Transform of S(n) = Jacobsthal(n+2) (cf. A001045). 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). - N. J. A. Sloane, Sep 05 2014

			May be arranged into blocks of sizes 1,1,2,4,8,16,...:
1,
3,
3, 5,
3, 9, 5, 11,
3, 9, 9, 15, 5, 15, 11, 21,
3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, ...
... - _N. J. A. Sloane_, Sep 05 2014
.
From _Omar E. Pol_, Mar 15 2015: (Start)
Apart from the initial 1, the sequence can be written also as an irregular tetrahedron T(s,r,k) = A001045(r+2) * a(k), s>=1, 1<=r<=s, 0<=k<=(A011782(s-r)-1) as shown below (see also _Joerg Arndt_'s equivalent program):
3;
..
3;
5;
.......
3,   9;
5;
11;
...............
3,   9,  9, 15;
5,  15;
11;
21;
...............................
3,   9,  9, 15,  9, 27, 15, 33;
5,  15, 15, 25;
11, 33;
21;
43;
..............................................................
3,   9,  9, 15,  9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63;
5,  15, 15, 25, 15, 45, 25, 55;
11, 33, 33, 55;
21, 63;
43;
85;
...
Note that every row r is equal to A001045(r+2) times the beginning of the sequence itself, thus in 3D every column contains the same number.
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..16383 (first 1024 terms from T. D. Noe)
Joerg Arndt, A071053 (number of odd terms in expansion of (1+x+x^2)^n), SeqFan Mailing List, Mar 09 2015.
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.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Janko Gravner and Alexander E. Holroyd, Percolation and Disorder-Resistance in Cellular Automata, Annals of Probability, volume 43, number 4, 2015, pages 1731-1776. Also arxiv:1304.7301 [math.PR], 2013-2015 and second author's copy. See Fig. 1.1 (left).
S. Kropf, S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
N. Pitsianis, P. Tsalides, G. L. Bleris, A. Thanailakis & H. C. Card, Deterministic one-dimensional cellular automata, Journal of Statistical Physics, 56(1-2), 99-112, 1989. [Discusses Rule 150]
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n [Cached copy, with permission]
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.
S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55 (1983), 601--644.
Index entries for sequences related to cellular automata

Cf. A038184, A118110, A071036, A001045, A253102, A020987, A246035, A245562, A087206.

a[n_] := Total[CoefficientList[(x^2 + x + 1)^n, x, Modulus -> 2]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 05 2018 *)

b(n) = { (2^n - (-1)^n) / 3; }  \\ A001045
a(n)=
{
    if ( n==0, return(1) );
    \\ Use  a( 2^k * t ) = a(t)
    n \= 2^valuation(n,2);
    if ( n==1, return(3) );  \\ Use a(2^k) == 3
    \\ now n is odd
    my ( v1 = valuation(n+1, 2) );
    \\ Use a( 2^k - 1 ) = A001045( 2 + k ):
    if ( n == 2^v1 - 1 ,  return( b( v1 + 2 ) ) );
    my( k2 = 1, k = 0 );
    while ( k2 < n,  k2 <<= 1; k+=1 );
    if ( k2 > n, k2 >>= 1; k-=1 );
    my( t = n - k2 );
    \\ here  n == 2^k + 1 where k maximal
    \\ Use the following:
    \\ a( 2^k + t ) =  3 * a(t)  if  t <= 2^(k-1)
    \\ a( 2^k + 2^(k-1) + t ) =  5 * a(t)  if  t <= 2^(k-2)
    \\ a( 2^k + 2^(k-1) + 2^(k-2) + t ) =  11* a(t)  if  t <= 2^(k-3)
    \\  ... etc. ...
    \\ a( 2^k + ... + 2^(k-s) + t ) = A001045(s+2) * a(t)  if  t <= 2^((k-1)-s)
    my ( s=1 );
    while ( 1 ,
        k2 >>= 1;
        if ( t <= k2 ,  return(  b(s+2) * a(t) ) );
        t -= k2;
        s += 1;
    );
}
\\ Joerg Arndt, Mar 15 2015, from SeqFan Mailing List, Mar 09 2015

a(n) = Product_{i in row n of A245562} A001045(i+2) [Sillke]. For example, a(11) = A001045(3)*A001045(4) = 3*5 = 15. - N. J. A. Sloane, Aug 10 2014
Floor((a(n)-1)/4) mod 2 = A020987(n). - Ralf Stephan, Mar 18 2004
a(2*n) = a(n); a(2*n+1) = a(n) + 2*a(floor(n/2)). - Peter J. Taylor, Mar 26 2020
Sum_{k = 0..2^n-1} a(k) = A087206(n). - Linhua Zou, Jun 13 2025

Entry revised by N. J. A. Sloane, Aug 13 2014

A139818 Squares of Jacobsthal numbers.

Original entry on oeis.org

0, 1, 1, 9, 25, 121, 441, 1849, 7225, 29241, 116281, 466489, 1863225, 7458361, 29822521, 119311929, 477204025, 1908903481, 7635439161, 30542106169, 122167725625, 488672300601, 1954686406201, 7818751217209, 31274993684025

Offset: 0

Paul Curtz, May 17 2008

Run length transform gives A246035. - N. J. A. Sloane, Feb 26 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
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, 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
Index entries for linear recurrences with constant coefficients, signature (3,6,-8).

Cf. A001045, A246035. First differences give (apart from signs) A083086.

[1/9-(2/9)*(-2)^n+(1/9)*4^n: n in [0..35]]; // Vincenzo Librandi, Aug 09 2011

LinearRecurrence[{3, 6, -8}, {0, 1, 1}, 25] (* Jean-François Alcover, Jan 09 2019 *)

concat (0, Vec(x*(1-2*x)/((1-x)*(1+2*x)*(1-4*x)) + O(x^30))) \\ Michel Marcus, Mar 04 2015

a(n) = 3*a(n-1) + 6*a(n-2) - 8*a(n-3).
a(n) = (A001045(n))^2.
G.f.: x*(1-2*x)/((1-x)*(1+2*x)*(1-4*x)).

More terms from R. J. Mathar, Dec 12 2009

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 *)

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 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 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 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.

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

Original entry on oeis.org

1, 6, 6, 20, 6, 36, 20, 88, 6, 36, 36, 120, 20, 120, 88, 336, 6, 36, 36, 120, 36, 216, 120, 528, 20, 120, 120, 400, 88, 528, 336, 1376, 6, 36, 36, 120, 36, 216, 120, 528, 36, 216, 216, 720, 120, 720, 528, 2016, 20, 120, 120, 400, 120, 720, 400, 1760, 88, 528, 528, 1760, 336, 2016, 1376, 5440

Offset: 0

N. J. A. Sloane, Aug 21 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 077 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link).
Run Length Transform of A246036.
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]
[0, 0, 0]
[X, X, X]
which contains a(1) = 6 ON cells.

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, A246035.

Cf. A246036.

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);
OddCA(f, 70);

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

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

Original entry on oeis.org

1, 7, 7, 29, 7, 49, 29, 103, 7, 49, 49, 203, 29, 203, 103, 373, 7, 49, 49, 203, 49, 343, 203, 721, 29, 203, 203, 841, 103, 721, 373, 1407, 7, 49, 49, 203, 49, 343, 203, 721, 49, 343, 343, 1421, 203, 1421, 721, 2611, 29, 203, 203, 841, 203, 1421, 841, 2987, 103, 721, 721, 2987, 373, 2611, 1407, 5277

Offset: 0

N. J. A. Sloane, Aug 21 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 575 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link).
Run Length Transform of A246038.
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]
[0, X, 0]
[X, X, X]
which contains a(1) = 7 ON cells.

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, 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.
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. A246037.

Cf. A246038.

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)+1 mod 2;
OddCA(f, 70);

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

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

Original entry on oeis.org

1, 9, 9, 37, 9, 65, 37, 157, 9, 81, 65, 237, 37, 293, 157, 713, 9, 81, 81, 333, 65, 473, 237, 1077, 37, 333, 293, 1129, 157, 1285, 713, 2737, 9, 81, 81, 333, 81, 585, 333, 1413, 65, 585, 473, 1733, 237, 1933, 1077, 4337, 37, 333, 333, 1369, 293, 2125, 1129, 4969, 157, 1413, 1285, 5041, 713, 5561, 2737, 11421, 9, 81

Offset: 0

N. J. A. Sloane, Aug 26 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 (a cross containing 9 cells), 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:
[0, 0, X, 0, 0]
[0, 0, X, 0, 0]
[X, X, X, X, X]
[0, 0, X, 0, 0]
[0, 0, X, 0, 0]
which contains a(1) = 9 ON cells.
The second and third generations are:
[0, 0, 0, 0, X, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, X, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[X, 0, X, 0, X, 0, X, 0, X]  (again with 9 ON cells)
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, X, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, X, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, X, X, 0, X, X, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, X, 0, 0, X, X, X, 0, 0, X, 0, 0]
[0, 0, X, 0, X, 0, 0, 0, X, 0, X, 0, 0]
[X, X, 0, 0, X, 0, X, 0, X, 0, 0, X, X] (with 37 ON cells)
[0, 0, X, 0, X, 0, 0, 0, X, 0, X, 0, 0]
[0, 0, X, 0, 0, X, X, X, 0, 0, X, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, X, X, 0, X, X, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
The terms can be arranged into blocks of sizes 1,1,2,4,8,16,32,...:
1,
9,
9, 37,
9, 65, 37, 157,
9, 81, 65, 237, 37, 293, 157, 713,
9, 81, 81, 333, 65, 473, 237, 1077, 37, 333, 293, 1129, 157, 1285, 713, 2737,
9, 81, 81, 333, 81, 585, 333, 1413, 65, 585, 473, 1733, 237, 1933, 1077, 4337, 37, 333, 333, 1369, 293, 2125, 1129, 4969, 157, 1413, 1285, 5041, 713, 5561, 2737, 11421, ...
The final terms in the rows are A246315.

Alois P. Heinz, Table of n, a(n) for n = 0..512

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

Cf. A246315, A247647, A247648, A247649.

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

c[f_] := f /. {x -> 1, y -> 1};
OddCA[f_, M_] := Module[{a = {}, f2, p = 1}, f2 = PolynomialMod[f, 2]; Do[ AppendTo[a, c[p]]; Print[a]; p = PolynomialMod[p f2, 2], {n, 0, M}]; a];
f = 1/x^2 + 1/x + 1 + x + x^2 + 1/y^2 + 1/y + y + y^2;
OddCA[f, 70] (* Jean-François Alcover, May 24 2020, after Maple *)

The values of a(n) for n in A247647 (or A247648) determine all the values, as follows. Parse the binary expansion of n into terms from A247647 separated by at least two zeros: m_1 0...0 m_2 0...0 m_3 ... m_r 0...0. Ignore any number (one or more) of trailing zeros. Then a(n) = a(m_1)*a(m_2)*...*a(m_r). For example, n = 37_10 = 100101_2 is parsed into 1.00.101, and so a(37) = a(1)*a(5) = 9*65 = 585. This is a generalization of the Run Length Transform.

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

Original entry on oeis.org

1, 6, 6, 22, 6, 36, 22, 82, 6, 36, 36, 132, 22, 132, 82, 302, 6, 36, 36, 132, 36, 216, 132, 492, 22, 132, 132, 484, 82, 492, 302, 1106, 6, 36, 36, 132, 36, 216, 132, 492, 36, 216, 216, 792, 132, 792, 492, 1812, 22, 132, 132, 484, 132, 792, 484, 1804, 82, 492, 492, 1804, 302, 1812, 1106, 4066

Offset: 0

N. J. A. Sloane, Jan 29 2015

nonn

This is the odd-rule cellular automaton defined by OddRule 175 (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, 0, X]
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, 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.
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, A253064, A253065, A253066.

Cf. A253070.

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

(* f = A253070 *) f[0]=1; f[1]=6; f[2]=22; f[3]=82; f[4]=302; f[5]=1106;f[6]=4066; f[n_] := f[n] = 8 f[n-4] + 8 f[n-3] + 3 f[n-1]; Table[Times @@ (f[Length[#]]&) /@ Select[Split[IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 63}] (* Jean-François Alcover, Jul 12 2017 *)

This is the Run Length Transform of A253070.

cp's OEIS Frontend

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A139818 Squares of Jacobsthal numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

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

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

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

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.