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

[Antti Karttunen]

On Thu, Apr 15, 2010 at 2:05 PM, Antti Karttunen
<antti.karttunen at gmail.com>wrote:

>
>
> On Thu, Apr 15, 2010 at 1:44 PM, Antti Karttunen <
> antti.karttunen at gmail.com> wrote:
>
>
>
>
>> So, for case 8x8 we have about 2^64 / 8 (dihedral group) / 64 (toroidal
>> rotations)
>> ~ 2^55 patterns to test.
>
>
> I'm probably oversimplifying and over-optimistic in that
> calculation. To shed some light on this, I wonder if there
> are "2D-analogues" for these sequences counting bracelets
> and necklaces:
> http://www.research.att.com/~njas/sequences/A000029<http://www.research.att.com/%7Enjas/sequences/A000029>
> &
> http://www.research.att.com/~njas/sequences/A000031<http://www.research.att.com/%7Enjas/sequences/A000031>
>
> (that is, computed for the toroidal NxN bit-arrays)?
>
>
I get  for the latter analogue a sequence that begins as (from offset=0):

1, 2, 7, 64, 4156, 1342208, 1908897152, 11488774559744, 288230376353050816,
29850020237398264483840, 12676506002282327791964489728,

Which is not currently in OEIS.
Also, ((2^(n^2))/Anewone(n)) / (n^2)
seems to converge towards 1, as expected (?).

Note that http://www.research.att.com/~njas/sequences/A002724
is an analogous sequence, where all kind
of permutations of matrix columns and rows
are allowed, while here I allow only "rotating
them in full cycles over the edges".


I computed it with the following Python-code:


def igcd(a,b):
  '''Compute the greatest common divisor of integers a & b.'''
  while(0 != b):
    ex_b = b;
    b = a % b;
    a = ex_b;

  return(a);


def ilcm(a,b):
  '''Compute the lest common multiple of integers a & b.'''
  return((a*b)/igcd(a,b));


def Anewone(n):
  '''Compute Anewone(n).'''
  if(0==n): return(1)

  n2 = n*n;
  z = 0;

  for i in range(n):
   for j in range(n):
    z += 2**(n2 / ilcm(n/igcd(n,i+1), n/igcd(n,j+1)));

  return(z/n2);

[Anewone(n) for n in range(11)]

That is, I employ the (Burnside's/Cauchy's)
orbit-counting lemma in quite a straightforward way:


(1/(n^2)) Sum_{i=1..n} Sum_{j=1..n}
     2^(n^2 / lcm(n/gcd(n,i), n/gcd(n,j)) )

There might be a few ways to make this more concise, or create a version
summing
instead over the divisors of n,
and then employing phi, and so on,
like in
http://www.research.att.com/~njas/sequences/A000031


Could somebody compute the same sequence
with either Maple, Mathematica or Pari?
(Or tell if there's something wrong with my
logic.)

Then, to proceed 2D-analogue of
http://www.research.att.com/~njas/sequences/A000029
one has to consider also the effects of
D_{2*4} (the symmetry group of square)
in addition to the direct product Z_n x Z_n
which was enough in the preceding example.


Cheers,

Antti Karttunen