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