cp's OEIS Frontend

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.

%I A246314 #24 May 24 2020 12:44:22
%S A246314 1,9,9,37,9,65,37,157,9,81,65,237,37,293,157,713,9,81,81,333,65,473,
%T A246314 237,1077,37,333,293,1129,157,1285,713,2737,9,81,81,333,81,585,333,
%U A246314 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 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.
%C A246314 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 A246314 Alois P. Heinz, <a href="/A246314/b246314.txt">Table of n, a(n) for n = 0..512</a>
%F A246314 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 A246314 Here is the neighborhood:
%e A246314 [0, 0, X, 0, 0]
%e A246314 [0, 0, X, 0, 0]
%e A246314 [X, X, X, X, X]
%e A246314 [0, 0, X, 0, 0]
%e A246314 [0, 0, X, 0, 0]
%e A246314 which contains a(1) = 9 ON cells.
%e A246314 The second and third generations are:
%e A246314 [0, 0, 0, 0, X, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, X, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A246314 [X, 0, X, 0, X, 0, X, 0, X]  (again with 9 ON cells)
%e A246314 [0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, X, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, X, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, X, X, 0, X, X, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, X, 0, 0, X, X, X, 0, 0, X, 0, 0]
%e A246314 [0, 0, X, 0, X, 0, 0, 0, X, 0, X, 0, 0]
%e A246314 [X, X, 0, 0, X, 0, X, 0, X, 0, 0, X, X] (with 37 ON cells)
%e A246314 [0, 0, X, 0, X, 0, 0, 0, X, 0, X, 0, 0]
%e A246314 [0, 0, X, 0, 0, X, X, X, 0, 0, X, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, X, X, 0, X, X, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
%e A246314 [0, 0, 0, 0, 0, 0, X, 0, 0, 0, 0, 0, 0]
%e A246314 The terms can be arranged into blocks of sizes 1,1,2,4,8,16,32,...:
%e A246314 1,
%e A246314 9,
%e A246314 9, 37,
%e A246314 9, 65, 37, 157,
%e A246314 9, 81, 65, 237, 37, 293, 157, 713,
%e A246314 9, 81, 81, 333, 65, 473, 237, 1077, 37, 333, 293, 1129, 157, 1285, 713, 2737,
%e A246314 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 A246314 The final terms in the rows are A246315.
%p A246314 C:=f->subs({x=1, y=1}, f);
%p A246314 # Find number of ON cells in CA for generations 0 thru M defined by rule
%p A246314 # that cell is ON iff number of ON cells in nbd at time n-1 was odd
%p A246314 # where nbd is defined by a polynomial or Laurent series f(x, y).
%p A246314 OddCA:=proc(f, M) global C; local n, a, i, f2, p;
%p A246314 f2:=simplify(expand(f)) mod 2;
%p A246314 a:=[]; p:=1;
%p A246314 for n from 0 to M do a:=[op(a), C(p)]; p:=expand(p*f2) mod 2; od:
%p A246314 lprint([seq(a[i], i=1..nops(a))]);
%p A246314 end;
%p A246314 f:=1/x^2+1/x+1+x+x^2+1/y^2+1/y+y+y^2;
%p A246314 OddCA(f, 70);
%t A246314 c[f_] := f /. {x -> 1, y -> 1};
%t A246314 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 A246314 f = 1/x^2 + 1/x + 1 + x + x^2 + 1/y^2 + 1/y + y + y^2;
%t A246314 OddCA[f, 70] (* _Jean-François Alcover_, May 24 2020, after Maple *)
%Y A246314 Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034, A246035, A246037.
%Y A246314 Cf. A246315, A247647, A247648, A247649.
%K A246314 nonn
%O A246314 0,2
%A A246314 _N. J. A. Sloane_, Aug 26 2014