[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;
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
More information about the SeqFan
mailing list