[seqfan] Re: Finding the longest period Life-patterns on nxn toroidal board?

[David Seal]

> On 05 June 2019 at 21:14 Rob Pratt <robert.william.pratt at gmail.com> wrote:
> 
> You can model the problem as finding a longest cycle in a directed graph
> with 2^(n^2) nodes and the same number of links. Each node corresponds to
> a 0-1 nxn matrix and has a link to its successor after applying the Life
> rules.  Because each node has outdegee 1, the cycles are just the strongly
> connected components.  For n = 1 to 5, I get maximum cycle lengths
> 1, 1, 1, 8, and 20, respectively.

Using a somewhat more sophisticated version of that technique, I get 24 for n=6, the only positions with period 24 being a glider making its way across the board at one diagonal step every 4 generations and so returning to where it started in 24 generations.

The more sophisticated technique is to look at equivalence classes under the 288 symmetries of the 6x6 board generated by:

* the 6 cyclic rotations of the rows;
* the 6 cyclic rotations of the columns;
* the 8 reflection/rotation symmetries of a non-toroidal square board.

The equivalence classes associated with the vast majority of the possible positions can be expected to contain 288 positions each, with a small number being associated with equivalence classes of size a proper divisor of 288 (ranging down to the equivalence classes of the completely empty board and of the completely full board. There could therefore be expected to a bit over 2^36 / 288 = 238,609,294.222... equivalence classes, so I expected to be able to store all of them in under 2 GB of memory (assuming each is stored in a 64-bit word), or maybe 3-6 GB including some additional information about each equivalence class, such as its 'child', i.e. which equivalence class contained the next generation of the position.

I could then identify 'orphans' (equivalence classes with no 'parents') and disregard their 'parent'/'child' relationships with their 'children' in the 'parent' counts. That would reduce 'parent' counts and so would find any 'second-order orphans' (i.e. equivalence classes with 'parents' but no 'grandparents') and disregard them similarly, and repeat the process disregarding higher and higher order 'orphans' until no further equivalence classes were disregarded. The remaining equivalence classes would then be the ones in the cycles of equivalence classes, for the same reason that Rob Pratt gives.

Some care needs to be taken about interpreting the resulting cycles, because the cycle length in the equivalence class graph may be a proper factor of the cycle length in the full position graph. Examples are a blinker, which has period 1 in the equivalence class graph but period 2 in the full position graph, and a glider, which has period 2 in the equivalence class graph but period 24 in the full position graph. This can be dealt with by choosing an arbitrary position in any equivalence class in the cycle and tracking its Life generations forward until one returns to the original position. I refer to the period in the full position graph as the 'full period' and the period in the equivalence class graph as the 'minimised period' (to reflect the fact that it is the minimum number of generations one needs to look at to make it clear that the position is in a cycle). 

I have now written and debugged (hopefully fully!) such a program. A brief summary of its results in case anyone wants to try confirming them:

Equivalence classes: 239,123,150
Equivalence classes disregarded as 'orphans': 239,122,799
 (of levels ranging up to 90)
Equivalence classes in cycles: 351
Number of cycles with minimised period 1, full period 1: 241
 (these are the "still life" positions)
Number of cycles with minimised period 1, full period 2: 39
Number of cycles with minimised period 1, full period 6: 3
Number of cycles with minimised period 2, full period 2: 10
Number of cycles with minimised period 2, full period 4: 6
Number of cycles with minimised period 2, full period 6: 1
Number of cycles with minimised period 2, full period 8: 1
Number of cycles with minimised period 2, full period 12: 1
Number of cycles with minimised period 2, full period 24: 1
Number of cycles with minimised period 3, full period 3: 3
Number of cycles with minimised period 3, full period 6: 1
Number of cycles with minimised period 4, full period 8: 3
Number of cycles with minimised period 4, full period 12: 1

I can supply more details if desired.

The program is written in C99 and optimised highly specifically for the 6x6 toroidal board, so I haven't confirmed any of the values Rob Pratt gives for n = 1 to 5. It could be modified to do other sizes of board, but significant amounts of work would be required on it either to adapt it to another specific size of board or to deal with different sizes more generally, and the latter would almost certainly slow it down significantly.

The obvious next target is the 7x7 toroidal board, but the number of equivalence classes for it can be similarly expected to be a bit over 2^49 / (7*7*8) = 1,436,096,819,952.326..., i.e. about six thousand times larger than for n=6. As a first approximation, this could be expected to increase both the execution time and memory requirements of the program by the same factor. That would raise the execution time of my desktop from a bit over 6 minutes to a bit under a month, which is long but feasible, but the memory requirement would grow from about 4 GB to about 24 TB, which certainly isn't! So n=7 will require a completely different program...

David