[seqfan] A few seqs related to the Game of Life on toroidal NxN board.

Antti Karttunen antti.karttunen at gmail.com
Thu Apr 15 12:44:58 CEST 2010


I think (some of) these sequences were worthwhile to compute:

a) On NxN toroidal board, the number of patterns that
die on the next generation. (I.e. this is the toroidal
analogue of http://www.research.att.com/~njas/sequences/A134963 )

b) On NxN toroidal board, the number of patterns that
will end to a non-dead stable state (i.e. with a period=1).

c) On NxN toroidal board, the number of patterns that
will end to a cyclic pattern with a period=k.

d) On NxN toroidal board, the number of stable patterns.
(including all-dead state).

e) On NxN toroidal board, the number of patterns that
are contained in some cycle of length k.
(and maybe also, a number of distinct cycles).

Note that many of these sequences are much more well-defined
than the corresponding seqs on the infinite board, where we might
not know whether some seemingly random-looking froth will eventually
result a periodic or stable pattern.

and the last, of the most practical interest to me,

f) The maximum cycle length possible on NxN toroidal board.

Why practical? Because, after a suggestion from my friend, I added to this
project (with 8x8 toroidal board)
http://www.iki.fi/kartturi/FPGA/esimes/life/HARDWARE_PHOTOS/pelikone.html
also a MIDI-output, so it plays a kind of "music", with any Life-pattern
that doesn't immediately die.

So far the longest cycle (on 8x8 toroidal board) seems to result from this
pattern

.....
..***
***..
.....

which gives a cycle of period 48.

However, it would be nice to do some exhaustive searching on this matter.
In the program, one could prune, not only the usual rotations and
reflections of square but also all the "toroidal rotations" (that is, any
one (aperiodic in both x- and y- directions) pattern
has about NxN distinct "toroidal displacements).
So, for case 8x8 we have about 2^64 / 8 (dihedral group) / 64 (toroidal
rotations)
~ 2^55 patterns to test. If one pattern takes about
20 ns to test (on my small FPGA-board), then counting a(8)
would take about 22 years, without any further intelligence or hardware.

What one can say about the last sequence? At least one easy pick:
a(4n) >= a(n), because if n x n toroidal board has a pattern with cycle
length k, then one can "tile" the 4n x 4n toroidal board with the same
pattern, resulting the same cycle length.


Yours,

Antti Karttunen



More information about the SeqFan mailing list