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.

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

Author

N. J. A. Sloane, Aug 26 2014

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

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.

Programs

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

Mathematica

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

Formula

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.