Non-iterative algorithm for the 1st game of life

Question

Consider a boolean array a[n]where each element is a cell. A cell becomes live (installed in true) in the next generation if one and only one neighboring cell is alive, otherwise it becomes dead (set to false). The first and last cells are considered neighbors.

Given the a[n]size of the array nand the positive integer t, I want to calculate a[n]after the t-th generation of evolution, but without using an iterative algorithm on t, which can be potentially very large.

What I observed: if we define a S_k(a[n])circular a[n]right shift by elements k. That is, a[0]it becomes a[k]after one shift, if 0 <= k < n. Define a[n] ^ b[n]as the element operation xor between two boolean arrays. If it w[n]is a boolean array, the next generation can be expressed by the symbol

r(w[n]) = S_{-1}(w[n]) ^ S_1(w[n])

The xor operator is ^associative and commutative. Using this property, the next few generations w[n]can be calculated using

r^2(w[n]) = ( S_{-2}(w[n]) ^ S_0(w[n]) ) ^ ( S_0(w[n]) ^ S_2(w[n]) )
          = S_{-2}(w[n]) ^ S_2(w[n])

If we allow s_j = S_{-j}(w[n]) ^ S_j(w[n]), there is a pattern

r(w[n]) = s_1
r^2(w[n]) = s_2
r^3(w[n]) = s_3 ^ s_1
r^4(w[n]) = s_4
...
r(s_m) = s_{m-1} ^ s_{m+1}

Also, s_n = 0(an array of zeros), since the full circular shift is the original array. How to use this to output a non-iterative expression r^t(w[n])?

Edit: template

[1]
[2]
[1,3]
[4]
[3,5]
[2,6]
[1,3,5,7]
[8]

Answer 1

- a_0 n Z/2Z.

a_1 :

a_1 = M.a_0 = |0 1 0 0 ... 0 0 0|  |a_01|
              |1 0 1 0 ... 0 0 0|  |a_02|
              |0 1 0 1 ... 0 0 0|  |a_03|
              ....
              |0 0 0 0 ... 0 1 0|  |... |
              |0 0 0 0 ... 1 0 1|  |... |
              |0 0 0 0 ... 0 1 0|  |a_0n|

, t :

a_t = M^t . a_0

M^t O(n^3.log(t)) .

Answer 2

, . Hashlife ' , .

:

• , int array: , .
• : , , , . , , .

Answer 3

, ...

:

1
 2 
1 3
   4
  3 5
 2   6
1 3 5 7
       8
      7 9
     6   a
    5     b
   4       c
  3   ???   d
 2           e
1 3 5 7 9 b d f
               g

If so, the simplest way, apparently, is to calculate r for the closest degree 2 <= t, then for the rest of (t '= t-2 ^ n), etc., then you will be up to O (log (t)). If??? the area is actually empty, you should be able to limit the steps to 3 (avoid 2 ^ n-1 by calculating the value to, then go one step).