Consider a Boolean array a[n], where each element is a cell. A cell becomes alive (set to true) in the next generation if one and only one adjacent cell is alive, otherwise it becomes dead (set to false). The first and last cell are considered neighbours.
Given a[n], the array size n, and a positive integer t, I wish to compute the a[n] after t'th generation of evolution, but without using any iterative algorithm on t, which can be potentially very large.
What I have observed: if we define S_k(a[n]) be a circular shift of a[n] to the right by k elements. That is, a[0] becomes a[k] after one shift if 0 <= k < n. Define a[n] ^ b[n] to be the element-wise xor operation between two boolean arrays. If w[n] is a Boolean array, the next generation can be expressed by
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 of w[n] can be computed by
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 let 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}
Moreover, s_n = 0 (the array of zeroes) since a full circular shift is the original array. How do I use this to derive a non-iterative expression of r^t(w[n])?
Edit: The pattern is
[1]
[2]
[1,3]
[4]
[3,5]
[2,6]
[1,3,5,7]
[8]
Let's represent your input as a column vector a_0 of size n of elements of Z/2Z.
You can compute the next generation vector, a_1 by using a matrix multiplication:
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|
Given this recurrence relation, you can compute the generation at time t using the formula:
a_t = M^t . a_0
And you can easily compute M^t in O(n^3.log(t)) using repeated squaring.