a too-short sequence related to Latin squares

hv at crypt.org hv at crypt.org
Wed Sep 8 03:02:51 CEST 2004

Sterten at aol.com wrote:
:>> How many n X n squares are there,  filled with
:>> the numbers 1...n, such that in row or column  k,
:>> for all k = 1...n, the number k appears at least  once?
:Brendan wrote:
:>Now sum m(K) over K and you got  it.  Piece of cake.  n=6 can be
:>done too (at most a few  hundred million Ks).
:1,6,2683,223041730,6009583845720101,81562450515482338061230306,  different 

I finally managed to get code working for this approach, and my code
confirms these values up to a(5), the last taking just over 3 minutes.
(In the terms of my previous email, this implies c_5_10(5) = 216231599554,
and the fact this gives an integer result offers some additional slightly
elliptical evidence in favour of the correctness of both approaches.)

:only 1,3,22,115,415,1165 different products for  n=1,2,..,6.
:n=7 takes some hours. I feel, that we could get another  speed-factor of n! ?!
:Also, we could first determine the number of ks, where  the row and column
:positions of the first appearance coincide. I.e. which lie  on the diagonal
:and no other k appears in the (k-1)*2 cells before it in  that
:row or  column.
:1,5,120,8831,1248696,275064055, different  Ks
:1,3,22,115,415,1165, different products

Caching products (and even powers) provided a lot of the speedup for
my version of this code. I'm currently looping over each of the n x n
locations to determine the power mix for each K, so this is taking
O(n^(2n+2)) iterations. I'm not sure how, but I can imagine it being
possible to avoid the extra n x n loop and somehow having the power
mix for a given K fall out in linear time, and I can imagine pruning
about half the Ks by spotting diagonal symmetry; I don't see where
an O(n!) speedup would come from though.

Hugo van der Sanden

More information about the SeqFan mailing list