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

[Allan Wechsler]

Explicit enumeration is harder, indeed. I have not been able to do much
better than the following:

Each underlying configuration can be represented as an MxN rectangle of
bits in a number of ways. Each way can be read as a string of MN bits, and
then interpreted as a binary integer. Select as canonical the
representation with the smallest such reading.

Now iterate over the 2^MN representations, produce the underlying
configuration, and star "reading" it in all the possible ways, comparing
the resulting values with the original. If you find any representation
whose value is less than the original, discard the original and go on to
the next representation. But if the original value turns out to be the
smallest possible, then it is canonical and should be listed.

This astronomical double loop can be optimized in many ways, but I don't
think the basic idea can be improved.

On Sat, Jun 1, 2019 at 5:18 AM <hv at crypt.org> wrote:

> Thanks, A222187 will also of course be treating the 2 x 2 cases 11 / 00
> and 10 / 10 as distinct, hence a(2) = 7.
>
> The linked A222188 is what I was really after though, to try and consider
> if I can come up with any remotely efficient algorithm to enumerate
> the distinct cases.
>
> Hugo
>
> Allan Wechsler <acwacw at gmail.com> wrote:
> :This is a job for the Frobenius-Burnside-Cauchy-Polya counting formula. I
> :am sure this sequence is in OEIS.
> :
> :[pauses for 15 minutes to work it out]
> :
> :OK, after working out F(4) = 34 by hand, I found A222187, "Number of
> :toroidal n X 2 binary arrays ...", which counts the number of cases we
> have
> :to try to find the longest-lived Life pattern on such an array. It doesn't
> :tell us how to enumerate them, though.
> :
> :
> :
> :On Fri, May 31, 2019 at 8:21 PM <hv at crypt.org> wrote:
> :
> :> Antti Karttunen <antti.karttunen at gmail.com> wrote:
> :> :Find the (representatives of) patterns that produce a maximal possible
> :> :cyclic sequence of patterns on nxn toroidal board, with Conway's
> :> :"Life" cellular automaton rules.
> :>
> :> I've started thinking about this, and am unsure if I've confused myself.
> :>
> :> On a 1 x n board the number of distinguishable starting positions seems
> :> to be A000029 (which makes sense). Richer results for Conway's Life
> :> start with a 7-cycle at n=7 (1101000, a 3-place glider), and 6- and
> :> 8-cycles at n=8.
> :>
> :> On a 2 x n board, the analagous sequence appears to start 1,3,6,13,33,74
> :> which is not in the OEIS.
> :>
> :> Have I miscalculated? If it needs to be added, what's a useful way to
> :> describe the 2D analogue of a bracelet?
> :>
> :> For reference, below are the 13 distinguishable results I find for n=3
> :> on a 2xn grid.
> :>
> :> Hugo
> :>
> :> ... (1)
> :> ...
> :>
> :> x.. (6 analogues, including itself)
> :> ...
> :>
> :> xx. (6)
> :> ...
> :>
> :> x.. (3)
> :> x..
> :>
> :> x.. (6)
> :> .x.
> :>
> :> xxx (2)
> :> ...
> :>
> :> xx. (12)
> :> x..
> :>
> :> xx. (6)
> :> ..x
> :>
> :> xxx (6)
> :> x..
> :>
> :> xx. (3)
> :> xx.
> :>
> :> xx. (6)
> :> x.x
> :>
> :> xxx (6)
> :> xx.
> :>
> :> xxx (1)
> :> xxx
> :>
> :> total: 64 = 2^6 analagues accounted for.
> :>
> :> END
> :>
> :> --
> :> Seqfan Mailing list - http://list.seqfan.eu/
> :>
> :
> :--
> :Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>