A160239 -id:A160239 - cp's OEIS frontend

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

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.

A255287 Number of 1's in expansion of F^n mod 3, where F = 1/(xy)+1/y+x/y+1/x+x+y/x+y+xy.

Original entry on oeis.org

1, 8, 8, 8, 64, 52, 8, 64, 101, 8, 64, 64, 64, 512, 404, 52, 416, 448, 8, 64, 233, 64, 512, 700, 101, 808, 992, 8, 64, 64, 64, 512, 416, 64, 512, 808, 64, 512, 512, 512, 4096, 3220, 404, 3232, 3224, 52, 416, 832, 416, 3328

Offset: 0

N. J. A. Sloane, Feb 21 2015

nonn

A255287 and A255288 together are a mod 3 analog of A160239.

			The pairs [no. of 1's, no. of 2's] are [1, 0], [8, 0], [8, 13], [8, 0], [64, 0], [52, 32], [8, 13], [64, 104], [101, 112], [8, 0], [64, 0], [64, 104], [64, 0], [512, 0], [404, 184], [52, 32], [416, 256], [448, 296], [8, 13], [64, 104], [233, 208], [64, 104], [512, 832], [700, 836], [101, 112], [808, 896], [992, 1081], ...

Cf. A160239, A255288-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;
F1:=1/(x*y)+1/y+x/y+1/x+x+y/x+y+x*y mod 3;
g:=(F,n)->expand(F^n) mod 3;
[seq(C3(g(F1,n))[1],n=0..60)];

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.

A245195 a(n) = 2^A014081(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 2, 4, 8, 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 2, 4, 8, 2, 2, 2, 4, 2, 2, 4, 8, 4, 4, 4, 8, 8, 8, 16, 32, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 2, 4, 8, 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16, 2, 2, 2, 4, 2

Offset: 0

N. J. A. Sloane, Jul 24 2014

This sequence provides a bridge between A245180 (and, presumably, A160239) and A014081.
See A245196 for more about this class of sequences.
Run length transform of A011782: 1,1,2,4,8,16,32,64,... - Chai Wah Wu, Oct 19 2016

Chai Wah Wu and Robert Israel, Table of n, a(n) for n = 0..10000
Robert Israel, Proof that A277560 is the same as A245195 [This will be modified to reflect the fact that the two sequences have now been merged]
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166 [math.CO], 2016.

Cf. A014081, A245180, A160239, A048896, A245196, A005725, A005940, A011782, A106737, A162510.

# This Maple program applies more generally to a sequence where the recurrence across a block is as follows. The parameters to be set are the sequence G(0), G(1), G(2), ... (the final terms in the blocks), and the multiplier m.
# For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then
# (if j=0) a(2^k-2^r) = G(k-r-1),
# (if j>0) a(2^k-2^r+j) = m*G(k-r-1)*a(j).
# Since Maple gives its lists an offset of 1, it is necessary to add 1 to the arguments of G.
# For the present sequence, G(n)=2^n and m=1.
G:=[seq(2^n,n=0..30)];
m:=1;
f:=proc(n) option remember; global m,G; local k,r,j,np;
if n <= 2 then G[0+1] elif n=3 then G[1+1]
elif n=4 then G[0+1] elif n=5 then m*G[0+1] elif n=6 then G[1+1] elif n=7 then G[2+1]
else
   k:=1+floor(log[2](n)); np:=2^k-n;
   if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;
   if j=0 then G[k-r-1+1]; else m*G[k-r-1+1]*f(j); fi;
fi;
end;
[seq(f(n),n=1..520)]:
# Setting G(n) = A083424(n) and m = 8 gives A245180. Setting G(n) = 2^n and m = 2 gives A048896.
A245195:=n->add(binomial(n,2*k)*binomial(n,k) mod 2, k=0..floor(n/2)): seq(A245195(n), n=0..200); # Wesley Ivan Hurt, Nov 01 2016

Table[Sum[Mod[Binomial[n, 2 k] Binomial[n, k], 2], {k, 0, n}], {n, 0, 85}] (* Michael De Vlieger, Oct 21 2016 *)

a(n) = 2^hammingweight(bitand(n, n>>1)) \\ Charles R Greathouse IV, Jul 16 2016

a(n) = sum(k=0, n, binomial(n, 2*k)*binomial(n,k) % 2); \\ Michel Marcus, Oct 21 2016

from _future_ import division
def A277560(n):
    return sum(int(not (~n & 2*k) | (~n & k)) for k in range(n//2+1))

def A245195(n): return 1<<(n&(n>>1)).bit_count() # Chai Wah Wu, Feb 11 2023

The entries may be arranged into blocks of sizes 1,2,4,8,...:
B_0: 1,
B_1: 1, 2,
B_2: 1, 1, 2, 4,
B_3: 1, 1, 1, 2, 2, 2, 4, 8,
B_4: 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16,
B_5: 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 2, 4, 8, 2, 2, 2, 4, 2, 2, 4, 8, 4, 4, 4, 8, 8, 8, 16, 32,
...
Consider the block B_{k-1} containing terms a(2^(k-1)), a(2^(k-1)+1), ..., a(2^k-1). It is convenient to index the terms working backwards from the next, 2^k-th, term. For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then
(if j=0) a(2^k-2^r) = 2^(k-r-1),
(if j>0) a(2^k-2^r+j) = 2^(k-r-1)*a(j).
a(n) = A162510(A005940(1+n)). - Antti Karttunen, Oct 29 2016
From Robert Israel, Nov 02 2016: (Start)
a(2*k)   = a(k).
a(4*k+1) = a(k).
a(4*k+3) = 2*a(2*k+1).
G.f. g(x) satisfies g(x) = x + (2*x+1)*g(x^2) - x*g(x^4). (End)
Also, a(n) = Sum_{k=0..floor(n/2)} ((binomial(n,2k)*binomial(n,k)) mod 2). - Chai Wah Wu, Oct 19 2016 and Robert Israel, Nov 04 2016. For proof, see the article by Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166, or the Robert Israel link.

Changed offset to 0, merged former entry A277560 from Chai Wah Wu (Oct 19 2016) with this sequence. - N. J. A. Sloane, Nov 05 2016

A245540 Partial sums of A245180.

Original entry on oeis.org

1, 2, 5, 6, 14, 17, 31, 32, 40, 48, 72, 75, 99, 113, 165, 166, 174, 182, 206, 214, 278, 302, 414, 417, 441, 465, 537, 551, 663, 715, 931, 932, 940, 948, 972, 980, 1044, 1068, 1180, 1188, 1252, 1316, 1508, 1532, 1724, 1836, 2252, 2255, 2279, 2303, 2375, 2399, 2591, 2663, 2999, 3013, 3125, 3237

Offset: 1

N. J. A. Sloane, Jul 26 2014

Cf. A245180, A160239, A245542.

b[n_] := b[n] = Which[n == 1, 1, Mod[n, 2] == 0, b[n/2], Mod[n, 4] == 3, 2b[(n-1)/2] + b[n-2], True, 8b[(n-1)/4]];
Accumulate[Array[b, 58]] (* Jean-François Alcover, Oct 01 2018 *)

a(n) = (A245542(n) - 1)/8. - Omar E. Pol, Mar 07 2015

A246031 Number of ON cells in 3-D cellular automaton described in Comments, after n generations.

Original entry on oeis.org

1, 26, 26, 124, 26, 676, 124, 1400, 26, 676, 676, 3224, 124, 3224, 1400, 10000, 26, 676, 676, 3224, 676, 17576, 3224, 36400, 124, 3224, 3224, 15376, 1400, 36400, 10000, 89504, 26, 676, 676, 3224, 676, 17576, 3224, 36400, 676, 17576, 17576, 83824, 3224, 83824, 36400, 260000, 124, 3224, 3224, 15376, 3224, 83824, 15376, 173600, 1400, 36400, 36400, 173600, 10000, 260000, 89504, 707008

Offset: 0

N. J. A. Sloane, Aug 16 2014; corrected Aug 21 2014

nonn

We work on the cells of the 3-D grid. Each cell has 26 neighbors, A cell is ON iff an odd number of its neighbors were ON at the previous generation. We start with a single ON cell.

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

			The entries form blocks of sizes 1,1,2,4,8,...:
1,
26,
26, 124,
26, 676, 124, 1400,
26, 676, 676, 3224, 124, 3224, 1400, 10000,
26, 676, 676, 3224, 676, 17576, 3224, 36400, 124, 3224, 3224, 15376, 1400, 36400, 10000, 89504,
26, 676, 676, 3224, 676, 17576, 3224, 36400, 676, 17576, 17576, 83824, 3224, 83824, 36400, 260000, 124, 3224, 3224, 15376, 3224, 83824, 15376, 173600, 1400, 36400, 36400, 173600, 10000, 260000, 89504, 707008
...
From _Omar E. Pol_, Mar 19 2015: (Start)
Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
1;
..
26;
...
26;
124;
..........
26,   676;
124;
1400;
.....................
26,   676, 676, 3224;
124,  3224;
1400;
10000;
............................................
26,   676,  676, 3224, 676,17576,3224,36400;
124,  3224, 3224, 15376;
1400, 36400;
10000;
89504;
..........................................................................................
26,   676,  676, 3224, 676,17576,3224,36400,676,17576,17576,83824,3224,83824,36400,260000;
124,  3224, 3224, 15376, 3224, 83824, 15376, 173600;
1400, 36400, 36400, 173600;
10000, 260000;
89504;
707008;
...
Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k).
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1022
Shalosh B. Ekhad, Details about A246031 and A246032
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

A 3-D analog of A160239 (2-D) and A255477 (4-D). Cf. A246032.

P := PolynomialRing(GF(2),3);
f := (1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z;
p := 1;
for i := 1 to 100 do
  p := p*f;
  print(#Terms(p));
end for; // Roman Pearce, Feb 18 2015

# This is a very inefficient program!
f:=expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2))-x*y*z;
g:=n->expand(f^n) mod 2;
h:=n->subs({x=1,y=1,z=1},g(n));
[seq(h(n),n=0..30)];
# Better program from Roman Pearce, Feb 18 2015:
f := Expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z) mod 2:
p := 1;
for i from 1 to 100 do
  p := Expand(p*f) mod 2;
  lprint(nops(p));
end do:

f = (1 + x + x^2)*(1 + y + y^2)*(1 + z + z^2) - x*y*z;
p = 1; Print[1];
Join[{1}, Table[p = Expand[p*f] // PolynomialMod[#, 2]&; Lp = Length[p]; Print[Lp]; Lp, 100]] (* Jean-François Alcover, Jan 17 2018 *)

This is the Run Length Transform of A246032 (see Comments).

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

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

Original entry on oeis.org

0, 0, 13, 0, 0, 32, 13, 104, 112, 0, 0, 104, 0, 0, 184, 32, 256, 296, 13, 104, 208, 104, 832, 836, 112, 896, 1081, 0, 0, 104, 0, 0, 256, 104, 832, 896, 0, 0, 832, 0, 0, 1400, 184, 1472, 1768, 32, 256, 932, 256, 2048, 2692, 296

Offset: 0

N. J. A. Sloane, Feb 21 2015

nonn

A255287 and A255288 together are a mod 3 analog of A160239.

			The pairs [no. of 1's, no. of 2's] are [1, 0], [8, 0], [8, 13], [8, 0], [64, 0], [52, 32], [8, 13], [64, 104], [101, 112], [8, 0], [64, 0], [64, 104], [64, 0], [512, 0], [404, 184], [52, 32], [416, 256], [448, 296], [8, 13], [64, 104], [233, 208], [64, 104], [512, 832], [700, 836], [101, 112], [808, 896], [992, 1081], ...

Cf. A160239, 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;
F1:=1/(x*y)+1/y+x/y+1/x+x+y/x+y+x*y mod 3;
g:=(F,n)->expand(F^n) mod 3;
[seq(C3(g(F1,n))[2],n=0..60)];

A246030 a(n) = (52^(2n)+(-2)^(n+1))/3.

Original entry on oeis.org

1, 8, 24, 112, 416, 1728, 6784, 27392, 109056, 437248, 1746944, 6991872, 27959296, 111853568, 447381504, 1789591552, 7158235136, 28633202688, 114532286464, 458130194432, 1832518680576, 7330078916608, 29320307277824, 117281245888512, 469124949999616, 1876499867107328, 7505999334211584

Offset: 0

N. J. A. Sloane, Aug 15 2014

Essentially 8 times A083424.

Equals A160239(2^n). - N. J. A. Sloane, Oct 04 2014

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 [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, 2015
N. J. A. Sloane, Illustration for a(4) = 416.
N. J. A. Sloane, Illustration for a(5) = 1728.
N. J. A. Sloane, Illustration for a(6) = 6784.
N. J. A. Sloane, Illustration for a(7) = 27392 (tiff).
N. J. A. Sloane, Illustration for a(7) = 27392 (png).
Index entries for sequences related to cellular automata
Index entries for linear recurrences with constant coefficients, signature (2,8).

Cf. A001045, A083424, A160239.

I:=[1,8]; [n le 2 select I[n] else 2*Self(n-1)+8*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Feb 20 2015

CoefficientList[Series[(1 + 6 x) / (1 - 2 x - 8 x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Feb 20 2015 *)

a(0)=1, a(1)=8; thereafter a(n)=2*a(n-1)+8*a(n-2).
G.f.: (1+6*x)/(1-2*x-8*x^2).
a(n) = A001045(n+2)^2 - A001045(n)^2. - J. Conrad, Apr 05 2023

cp's OEIS Frontend

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

A255287 Number of 1's in expansion of F^n mod 3, where F = 1/(x*y)+1/y+x/y+1/x+x+y/x+y+x*y.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

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

A245195 a(n) = 2^A014081(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A245540 Partial sums of A245180.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A246031 Number of ON cells in 3-D cellular automaton described in Comments, after n generations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A255287 Number of 1's in expansion of F^n mod 3, where F = 1/(xy)+1/y+x/y+1/x+x+y/x+y+xy.

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

A246030 a(n) = (52^(2n)+(-2)^(n+1))/3.