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

[hv at crypt.org]

I'm worried that the canonicalization will itself be too slow to make
sense to do on all 2^(MN) combinations: if possible, I'd like to find
an approach that could potentially get up to around 16 x 16.

I need to do some experiments to see how much it gains, but I think it
should be possible to do something like:
- enumerate the distinguishable arrangements for a single 1 x N row;
- order and index them;
- create a lookup for the 2^N combinations to associate each with the
index of its canonical form;
- for each canonical row, select it as the first row; for each of the
remaining rows, select only those of the 2^N combinations that map to
a canonical index less than that of the first row (or the same index,
as long as none of the preceding rows have had a lesser index).

That doesn't prune out every non-canonical arrangement, but I think
it should be a good start, and should be much faster than a full
canonicalization of every possible arrangement.

Hugo

Allan Wechsler <acwacw at gmail.com> wrote:
: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/
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/