[seqfan] Re: Squares with prime sums in rows and columns

[Maximilian Hasler]

Obviously one gets the same row-column sum combination
for the n!^2*2 different configurations that are obtained from
a given configuration by applying any of the n! possible
permutations of columns and/or rows and optionally (for n>1,
else no factor 2) a transposition of the square (a[i,j] <-> a[j,i]).

That's why, for n=3, all "repetition counts" are a multiple of 3!^2*2=72.

So one can restrict the computations to one representative of each
equivalence class of positions modulo the above transformations.
I think this can be done by imposing the following restrictions:
* a[1,1]=1  (start with 1)
* a[1,i] < a[1,j] for i < j (1st row increasing)
* a[i,1] < a[j,1] for i < j (1st col. increasing)
* a[1,2] < a[2,1] (to "fix" w.r.t. transposition)

(If this is correct)
This would cut down the number of (potentially) inequivalent positions
to (n^2)!/n!^2/2 (sorry for the A/B/C...)
which means 5040 instead of 362880 for n=3
and 18162144000 (= 18e9) instead of 20922789888000 (=2e13)
for n=4 (which remains somehow large for a brute force approach...)

Maximilian
PS: the sequence a(n)=(n^2)!/n!^2/2 for n>1,
[1, 3, 5040, 18162144000, 538583682060103680000, ...]
seems not in OEIS, so I consider submitting it;
any useful comments are welcome.

On Sun, Oct 25, 2009 at 6:40 PM, Christopher Gribble
<chris.eveswell at virgin.net> wrote:
> Hi Zak,
>
> Here are some preliminary findings from generating each permutation of
> 1..N^2 and calculating the row and column sums of the corresponding square:
>
> N       N^2               (N^2)!        No. of distinct row-column sum
> combinations
>
> 1         1                  1            1
> 2         4                 24            3
> 3         9             362880          820
> 4        16     20922789888000            ? (might take some time to
> compute)
>
> {1, 3, 820, ...} is not in the OEIS.
>
> For N = 2, the distinct row-column sum combinations are
>
>  3    4    6    7
>  3    5    5    7
>  4    5    5    6
>
> Each combination is produced by 8 different squares.
>
> For N = 3, the distinct row-column sum combinations are too numerous to list
> here but I can supply them if anyone is interested.
>
> The frequencies with which the different repetition counts occur for the
> 820 row-sum combinations are:
>
> Repetition Count                Frequency
>          72                          82
...
>        2232                           1
>
> Of the 820 combinations, there are 4 that consist of all primes:
>
>                                                Repeat Count
>   7   13   13   19   19   19                   216
>  11   11   11   17   17   23                   288
>  11   11   17   17   17   17                   792
>  13   13   13   13   19   19                   360
>
> Best regards,
>
> Chris Gribble