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

%I #24 May 24 2020 12:44:22

%S 1,9,9,37,9,65,37,157,9,81,65,237,37,293,157,713,9,81,81,333,65,473,

%T 237,1077,37,333,293,1129,157,1285,713,2737,9,81,81,333,81,585,333,

%U 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

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

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

%H Alois P. Heinz, <a href="/A246314/b246314.txt">Table of n, a(n) for n = 0..512</a>

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

%e Here is the neighborhood:

%e [0, 0, X, 0, 0]

%e [0, 0, X, 0, 0]

%e [X, X, X, X, X]

%e [0, 0, X, 0, 0]

%e [0, 0, X, 0, 0]

%e which contains a(1) = 9 ON cells.

%e The second and third generations are:

%e [0, 0, 0, 0, X, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, X, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, 0, 0, 0]

%e [X, 0, X, 0, X, 0, X, 0, X] (again with 9 ON cells)

%e [0, 0, 0, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, X, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, X, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, X, X, 0, X, X, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

%e [0, 0, X, 0, 0, X, X, X, 0, 0, X, 0, 0]

%e [0, 0, X, 0, X, 0, 0, 0, X, 0, X, 0, 0]

%e [X, X, 0, 0, X, 0, X, 0, X, 0, 0, X, X] (with 37 ON cells)

%e [0, 0, X, 0, X, 0, 0, 0, X, 0, X, 0, 0]

%e [0, 0, X, 0, 0, X, X, X, 0, 0, X, 0, 0]

%e [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, X, X, 0, X, X, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]

%e [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]

%e The terms can be arranged into blocks of sizes 1,1,2,4,8,16,32,...:

%e 1,

%e 9,

%e 9, 37,

%e 9, 65, 37, 157,

%e 9, 81, 65, 237, 37, 293, 157, 713,

%e 9, 81, 81, 333, 65, 473, 237, 1077, 37, 333, 293, 1129, 157, 1285, 713, 2737,

%e 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, ...

%e The final terms in the rows are A246315.

%p C:=f->subs({x=1, y=1}, f);

%p # Find number of ON cells in CA for generations 0 thru M defined by rule

%p # that cell is ON iff number of ON cells in nbd at time n-1 was odd

%p # where nbd is defined by a polynomial or Laurent series f(x, y).

%p OddCA:=proc(f, M) global C; local n, a, i, f2, p;

%p f2:=simplify(expand(f)) mod 2;

%p a:=[]; p:=1;

%p for n from 0 to M do a:=[op(a), C(p)]; p:=expand(p*f2) mod 2; od:

%p lprint([seq(a[i], i=1..nops(a))]);

%p end;

%p f:=1/x^2+1/x+1+x+x^2+1/y^2+1/y+y+y^2;

%p OddCA(f, 70);

%t c[f_] := f /. {x -> 1, y -> 1};

%t 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];

%t f = 1/x^2 + 1/x + 1 + x + x^2 + 1/y^2 + 1/y + y + y^2;

%t OddCA[f, 70] (* _Jean-François Alcover_, May 24 2020, after Maple *)

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

%Y Cf. A246315, A247647, A247648, A247649.

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Aug 26 2014