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

Antti Karttunen antti.karttunen at gmail.com
Sun Apr 18 19:25:32 CEST 2010

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;


def ilcm(a,b):
  '''Compute the lest common multiple of integers 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)));


[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
instead over the divisors of n,
and then employing phi, and so on,
like in

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

Then, to proceed 2D-analogue of
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.


Antti Karttunen

More information about the SeqFan mailing list