login
Number of ON cells after n generations in a 2-dimensional "Odd-Rule" cellular automaton on triangular tiling.
2

%I #45 Nov 27 2016 21:03:15

%S 1,3,7,9,7,21,25,27,7,21,49,63,25,75,103,81,7,21,49,63,49,147,175,189,

%T 25,75,175,225,103,309,409,243,7,21,49,63,49,147,175,189,49,147,343,

%U 441,175,525,721,567,25,75,175,225,175,525,625,675,103,309,721

%N Number of ON cells after n generations in a 2-dimensional "Odd-Rule" cellular automaton on triangular tiling.

%C Each triangular tile has 3 neighbors. A cell is ON in a given generation if and only if there was an odd number of ON cells among the three nearest neighbors in the preceding generation.

%C At the initial moment there is a single ON cell.

%C Given pattern replicates after a number of generations which is a power of 2 when a(n) = 7.

%C Number of cells on each even step minus one is divisible by 6.

%C By analogy with the Ekhad, Sloane, Zeilberger link, one may suppose that using ternary expansion of n, recurrence relations for a(n) can be obtained and proved.

%C From _Andrey Zabolotskiy_, Aug 04 2016: (Start)

%C If the first conjecture from the Formula section is true then the fact that the right border of the triangle (see Example) gives A000244 follows directly from it.

%C If the second conjecture is true then the numbers just before the right border give A102900.

%C Since the 7 cells which are ON at the beginning of every row are farther and farther away from each other, the n-th term of a row (with offset 0) is a(n)*7 for not very large n.

%C See also comments to A247666.

%C (End)

%H Kovba Alexey, <a href="/A275667/a275667.pdf">Illustration for n = 0..5</a>

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.01796">A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata</a>, arXiv:1503.01796 [math.CO], 2015.

%H <a href="/wiki/Index_to_OEIS:_Section_Ce#cell">Index to sequences in the OEIS related to cellular automata</a>

%F a(0) = 1. Conjecture: a(2*t+1) = 3*a(t).

%F Conjectures: a(8*t+6) = 3*a(4*t+2) + 4*a(2*t), a(8*t+2) = 3*a(4*t) + 4*a(2*t), a(4*t) = a(2*t). These conjectured formulas together give recurrent relations for a(n) for any n. Also, obviously a(2*n) = A247666(n). - _Andrey Zabolotskiy_, Aug 04 2016

%e From _Omar E. Pol_, Aug 04 2016: (Start)

%e Written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:

%e 1;

%e 3;

%e 7, 9;

%e 7, 21, 25, 27;

%e 7, 21, 49, 63, 25, 75, 103, 81;

%e 7, 21, 49, 63, 49, 147, 175, 189, 25, 75, 175, 225, 103, 309, 409, 243;

%e ...

%e It appears that the right border gives A000244.

%e (End)

%Y Cf. A160239 (square tiling analog), A247640, A247666 (hexagonal tiling analogs).

%Y Cf. A000244, A011782, A102900.

%K nonn,tabf

%O 0,2

%A _Kovba Alexey_, Aug 04 2016