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
:matrices
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