Mail from Mark Garry (includes program in C)
Place the natural numbers between 1 and mn in a table of m rows by n columns, so that the sum of the addition of the products of the numbers that compose the rows plus the addition of the products of the numbers that compose the columns is as low as possible.
The minimum number occurs if the product of the numbers that compose the rows (or columns) are all the same value (this is impossible, so it is a lower bound). The lower bound can be easily computed.
The product of the numbers in the table is (mn)!, then, if all products of the numbers in the different rows have the same value, each product would be
(mn)!1/m
There are m rows, so:
m [(mn)!1/m]
Similarly, the lower bound of the sum of the products of the numbers in the columns are:
n [(mn)!1/n]
The lower bound of the grand total will be:
m [(mn)!1/m] + n [(mn)!1/n]
These values can be found in the table of lower bounds.
The records for each type of table can be found by choosing its dimension in the table of contents.
The score shown below each table is calculated as the quotient of the logarithms of the sum of products and the difference between that sum and the lower bound.
There is a relationship between the difference between the sum of products and the lower bound and the variance of products.
p is approximately equal to n2 V2 S
where p is the difference above mentioned, n is the number of rows, V is the variance and S is the sum of the products of the rows.
As an example, in the 6 × 6 case, n = 6, V = 189 466 320, S = 50 883 192, so p = 67.
If you find a table whose grand total is less than the grand total found here, please send me a e-mail. Your name and table will be placed in this page.
In a message dated 97-07-16 09:33:17 EDT, you write:
> I included your work in my page. Thank you very much.
>
> I didn't have time to double-check your results, so I blindly put them
> in my page.
I must apologize due to an error in the last version I sent.
In particular, the "smallest" variable was not being set high
enough to start with, and the program reported better soln's
than were actually possible in a number of cases (e.g.,
tables 2-6 2-7 2-8 3-8 4-7 4-8 5-6 5-7).
Below I have attached a new set of minimums. Where you see the
message "soln not possible", it means there was no
possible row/column match for the numeral 1. As such, the
program increased the ranges and searched again. (*yes,
I decided to add the extra check.)
- Mark
2 2
Used 0 slack for solution of 10 with 1 combinacions
Soln not possible, increasing slacks to 1 1
The best possible solution is 21
2 3
Used 0 slack for solution of 54 with 2 combinacions
Used 1 slack for solution of 28 with 3 combinacions
The best possible solution is 83
2 4
Used 0 slack for solution of 402 with 2 combinacions
Used 3 slack for solution of 60 with 3 combinacions
44525.35 12:22:05 07/16/19
2 5
Used 0 slack for solution of 3810 with 3 combinacions
Used 7 slack for solution of 110 with 1 combinacions
The best possible solution is 3920
2 6
Used 3 slack for solution of 43776 with 5 combinacions
Used 14 slack for solution of 182 with 12 combinacions
The best possible solution is 43958
2 7
Used 0 slack for solution of 590520 with 8 combinacions
Used 24 slack for solution of 280 with 7 combinacions
The best possible solution is 590800
2 8
Used 32 slack for solution of 9148320 with 14 combinacions
Used 38 slack for solution of 408 with 23 combinacions
The best possible solution is 9148728
3 3
Used 0 slack for solution of 214 with 1 combinacions
Soln not possible, increasing slacks to 1 1
Soln not possible, increasing slacks to 2 2
Soln not possible, increasing slacks to 3 3
Soln not possible, increasing slacks to 4 4
The best possible solution is 436
3 4
Used 0 slack for solution of 2348 with 3 combinacions
Used 2 slack for solution of 594 with 4 combinacions
Soln not possible, increasing slacks to 1 1
Soln not possible, increasing slacks to 2 2
Soln not possible, increasing slacks to 3 3
Soln not possible, increasing slacks to 4 4
The best possible solution is 2946
3 5
Used 1 slack for solution of 32808 with 26 combinacions
Used 8 slack for solution of 1334 with 11 combinacions
The best possible solution is 34142
3 6
Used 4 slack for solution of 557064 with 19 combinacions
Used 28 slack for solution of 2614 with 26 combinacions
The best possible solution is 559678
3 7
Used 21 slack for solution of 11131920 with 92 combinacions
Used 68 slack for solution of 4645 with 17 combinacions
The best possible solution is 11136565
3 8
Used 15 slack for solution of 255872240 with 33 combinacions
Used 139 slack for solution of 7676 with 3 combinacions
The best possible solution is 255879916
4 4
Used 1 slack for solution of 8556 with 27 combinacions
The best possible solution is 17112
4 5
Used 1 slack for solution of 157978 with 45 combinacions
Used 0 slack for solution of 23780 with 33 combinacions
The best possible solution is 181758
4 6
Used 2 slack for solution of 3550068 with 538 combinacions
Used 0 slack for solution of 55412 with 1 combinacions
The best possible solution is 3605480
4 7
Used 20 slack for solution of 93992952 with 34 combinacions
Used 1 slack for solution of 114058 with 8 combinacions
The best possible solution is 94107010
4 8
Used 81 slack for solution of 2864856944 with 13 combinacions
Used 2 slack for solution of 214100 with 1256 combinacions
The best possible solution is 2865071044
5 5
Used 1 slack for solution of 545884 with 225 combinacions
The best possible solution is 1091768
5 6
Used 12 slack for solution of 15265196 with 797 combinacions
Used 0 slack for solution of 1520879 with 7 combinacions
The best possible solution is 16786075
5 7
Used 28 slack for solution of 503287980 with 29348 combinacions
Used 5 slack for solution of 3642652 with 29000 combinacions
The best possible solution is 506930632
6 6
Used 4 slack for solution of 50883129 with 160 combinacions
The best possible solution is 101766258
6 7
Used 12 slack for solution of 2008002684 with 1 combinacions
Used 6 slack for solution of 141876097 with 6827 combinacions
The best possible solution is 2149878781
------------------------------------------( program )---------------------
/*
* Program to calculate lower bounds for the following:
* Take a table of number with X rows and Y columns
* Multiply the Y numbers in each row and sum across all X rows
* Multiply the X numbers in each col and sum across all Y cols
* Add the two together ... this is what we want to minimize.
*
* Program Version 2.1
* Written by M.Garry July, 1997
*
* Next steps:
* Combine each row solution across each column solution,
* If it fits, you have the solution. If not raise the hurdle.
* We already test the rows and columns
* that contain a "1" since these are the first row and and the
* first column in each combination. To test, we subtract 1 from
* row bitmap1[] and use the existing "exist" subroutine. If
* they are compatible, they should now having nothing left
* in common, and the "exist" return value will be 1 (true).
* This is extremely fast, and would immediately find
* a number non-compatibilities, since the "1" is the
* most difficult number to place in the matrix.
*
*
* Notes:
* A 6 by 6 matrix of numbers takes 6 seconds to execute.
* A 3 by 7 takes longer due to combinations and poor initial fit
* (Based on P5-133 w/DJGPP)
*/
/*
* Special note: Watch out for compilers that use 16 bit integers
* because they will not calc b*32*33*34*35*36 correctly, since the
* 32*33*34*35*36 may be precompiled as "int" versus "long int".
* Also, for cases where the min_rows > 2^31, I do not yet trust the
* output (even with long double) since the sums may periodically
* drop some places due to rounding to 32 place accuracy. M.Garry v2.0
*/
/*----------------( INCLUDES )----------------*/
#include <stdio.h>
#include <math.h>
/*----------------( DEFINES )----------------*/
#define cant 40000
#define tam 9
/*----------------( GLOBALS )----------------*/
int comb[cant][tam]; /* the #'s stored in each possible row */
long double prod[cant]; /* the product for a single row */
long double proda[cant]; /* the product for a single row */
long double prodr[cant]; /* the product for a single row */
long double prodc[cant]; /* the product for a single row */
unsigned long bitmap1[cant];
unsigned long bitmap2[cant];
unsigned long row1[cant];
unsigned long row2[cant];
unsigned long col1[cant];
unsigned long col2[cant];
int rows; /* number of rows in matrix */
int cols; /* number of cols in matrix */
int n[10]; /* Numbers being placed in a row */
long double min_row; /* The min row product */
long double min_col; /* The min col product */
long double max_row; /* The max row product */
long double max_col; /* The max col prodcut */
long double min_tot; /* The minimum sum of rows & cols */
int slack; /* the amount above the bare minimum */
int u; /* 1 + the number of possible rows */
int u1; /* below u1, all bitmaps have a "1" */
long unsigned maximo; /* limit used to find possible rows */
long unsigned minimo; /* limit used to find possible rows */
long double smallest; /* the smallest row solution found */
long double limit; /* the largest row solution allowed */
int stopper; /* the number of solutions <= smallest */
int combo[10][cant]; /* progressively passed solutions */
int saved[10][cant]; /* progressively passed solutions */
int row3[10][cant]; /* progressively passed solutions */
int col3[10][cant]; /* progressively passed solutions */
long double factorial; /* The (rows*cols) factorial */
/*
* The rows and columns will be limited to fit within bounds
* If they exceed these bounds, a solution may be found, but
* it is theoretically possible that a better solution could
* be found if slack were increased first.
*/
long double min_rows; /* The limit for the rows */
long double min_cols; /* The limit for the cols */
/* Checks if two bitmaps overlap in any bits */
int exist(int i,int j)
{
if( bitmap1[i] & bitmap1[j] ) return 0;
if( bitmap2[i] & bitmap2[j] ) return 0;
return 1;
}
/* Calcs the basic requirement for overall size */
void basic_mins(int rows,int cols)
{
double rd = (double) rows;
double cd = (double) cols;
long double min_tot; /* The minimum sum of rows & cols */
double t; /* temp storage */
int i;
factorial=1; /* The (rows*cols) factorial */
for( i=rows*cols; i > 1; i-- )
factorial *= (double) i;
min_rows = ceil( rd * pow( factorial , 1./rd ) ) + slack;
min_cols = ceil( cd * pow( factorial , 1./cd ) ) + slack;
min_tot = min_rows + min_cols - slack;
for( t = ceil(min_rows/rd); ; t++ )
if( t + ceil((rd-1.)*pow(factorial/t,1./(rd-1.))) > min_rows ) break;
max_row = t-1;
for( t = ceil(min_rows/rd); ; t-- )
if( t + ceil((rd-1.)*pow(factorial/t,1./(rd-1.))) > min_rows ) break;
min_row = t+1;
for( t = ceil(min_cols/cd); ; t++ )
if( t + ceil((cd-1.)*pow(factorial/t,1./(cd-1.))) > min_cols ) break;
max_col = t-1;
for( t = ceil(min_cols/cd); ; t-- )
if( t + ceil((cd-1.)*pow(factorial/t,1./(cd-1.))) > min_cols ) break;
min_col = t+1;
/* Printing functions */ /*
printf("\n Basic analysis on the %d by %d table...\n",rows,cols);
printf(" Total Sum >= %15.0Lf (slack added=%d)\n",min_tot,slack);
printf(" Sum of rows >= %15.0Lf\n",min_rows);
printf(" Sum of cols >= %15.0Lf\n",min_cols);
printf(" %.0Lf <= col <= %.0Lf\n",min_col,max_col);
printf(" %.0Lf <= row <= %.0Lf\n",min_row,max_row);
*/
}
/* Calc's the possible 1-d (row or col) combinations that can fit */
void oneway(level, maxlevel, n1, prod1, rowcol)
int level; /* location of number we are placing */
int maxlevel; /* Number of numbers we are placing */
int n1; /* The lowest number to consider */
long unsigned prod1; /* the cum product for the placed #s */
int rowcol; /* The largest number possible = row*col
*/
{
int unplaced = maxlevel-level; /* the numbers to be placed later in row
*/
int n2; /* the # being placed at this level */
long unsigned minprod;
long unsigned maxprod;
long unsigned prod2;
int i,j;
for( n2=n1; n2 <= rowcol-unplaced; n2++) { /* all possible positions */
minprod = maxprod = prod2 = prod1 * n2; /* current row product */
for(i=1;i <= unplaced;i++) {
minprod *= (n2+i);
maxprod *= (rowcol+1-i);
}
if( maxprod < minimo ) continue;
if( minprod > maximo ) return;
n[level] = n2;
if( level<maxlevel ) {
oneway( level+1, maxlevel, n2+1, prod2, rowcol);
} else {
bitmap1[u] = 0;
bitmap2[u] = 0;
for ( j=1; j <= level; j++) {
comb[u][j]=n[j];
if( n[j] < 33 ) {
bitmap1[u] |= (1 << (n[j]-1));
} else {
bitmap2[u] |= (1 << (n[j]-33));
}
prod[u] = prod2;
if( n[1] == 1 ) u1 = u;
}
/* Printing functions */ /*
printf("%d) ",u);
for( j=1; j <= level; j++) printf("%d ",n[j]);
printf(" %ld\n",prod2);
fflush(stdout);
*/
if( ++u > cant+1 ) {printf("Increase cant!!");exit(0);}
}
}
}
/* Compares all 1-d combos to ensure they are compatible with each other */
void step2(level,maxlevel,num_in)
int level; /* location of row/col we are placing */
int maxlevel; /* Number of rows/cols we are placing */
int num_in; /* Number of combinations to try */
{
/*
* Procedure ... Select a combo
* Find all compatible combos, and keep record of them
* Then choose one of the compatible combos and repeat
*/
int i,j;
int num_out;
long unsigned a;
int unplaced = maxlevel-level; /* # of rows/cols to be placed later */
for( i=0; i < num_in-unplaced; i++) {
n[level] = i;
num_out = 0;
for( j=i+1; j < num_in; j++)
if( exist(combo[level][i],combo[level][j]) )
combo[level+1][num_out++] = combo[level][j];
if( level < maxlevel ) {
step2(level+1,maxlevel,num_out);
} else {
a = 0;
for( j=1;j <= level;j++ ) a+=prod[combo[j][n[j]]];
if (a <= limit) {
if( ++stopper > cant+1 ) {printf("Error --- increase
cant");exit(0);}
if (a < smallest) smallest = a;
/* Save info for 2-d comparison */
for( j=1;j <= level;j++ ) saved[j][stopper] = combo[j][n[j]];
proda[stopper] = a;
/* Printing functions */ /*
printf("%d) Combinacion",stopper);
for( j=1; j <= level; j++) printf(" %d",combo[j][n[j]]);
printf(" Total: %ld \n",a);
*/
}
}
}
}
/* Initializes comparison, then calls step2() */
void step2a(level,maxlevel,num_in)
int level; /* location of row/col we are placing */
int maxlevel; /* Number of rows/cols we are placing */
int num_in; /* Number of combinations to try */
{
/*
* Procedure ... Select a combo
* Find all compatible combos, and keep record of them
* Then choose one of the compatible combos and repeat
*/
int i,j;
int num_out;
smallest = limit = min_rows+1; /* if this is exceeded, a smaller
* solution may be possible at higher
* levels of slack!
*/
for( i=0; i <= u1; i++) { /* below "u1" all have a "1" */
n[1] = i;
num_out = 0;
combo[1][i]=i;
for( j=u1+1; j < num_in; j++) /* below "u1" all have a "1" */
if( exist(i,j) )
combo[2][num_out++] = j;
step2(2,maxlevel,num_out);
}
}
/* The main routine to call the others */
void crunch(int calcslack)
{
long double base; /* used to see how "far we got" */
for( stopper=0; stopper < 1 ;slack+=3 ) {
/* printf("\n\n*** Slack allowed = %d\n\n",slack); */ /* Prints periodic
updates to screen */
basic_mins(rows,cols);
if( slack < 1 ) base = min_rows;
minimo = min_row;
maximo = max_row;
u=0;
u1=-1;
oneway( 1, cols, 1, 1, rows*cols);
if( u1 == -1 ) continue; /* No soln's with a "1" exist */
step2a(1,rows,u);
}
if( !calcslack ) {
slack = smallest-base;
printf("Used %d slack for solution of %.0Lf with %d
combinacions\n",slack,smallest,stopper);
}
}
/* Gets user input when desired */
int main(void)
{
int i,t,r,c;
int soln=0;
int slack_r;
int slack_c;
int stopper_r;
int stopper_c;
int calc_r_slack=0;
int calc_c_slack=0;
long double bestsoln;
printf("Enter the number of rows & columns: ");
scanf("%d %d",&rows,&cols);
slack_r = slack_c = 0;
l1:
slack=slack_r;
crunch(calc_r_slack);
/* Save row info */
stopper_r = stopper;
if(!calc_r_slack) slack_r = slack;
calc_r_slack=1;
/* printf(" Column Bitmaps being saved: "); */
for( i=0; i < u; i++ ) { /* save the entries in the rows */
row1[i] = bitmap1[i];
row2[i] = bitmap2[i];
/* printf(" %ld-%ld",bitmap1[i],bitmap2[i]); */
}
for( i=1; i <= stopper; i++ ) { /* save the valid combos of rows */
prodr[i] = proda[i];
for( c=1; c <= cols; c++ )
row3[c][i] = saved[c][i];
}
if( rows != cols ) {
t = rows;
rows = cols;
cols = t;
slack=slack_c;
crunch(calc_c_slack);
}
/* Save col info */
stopper_c = stopper;
if(!calc_r_slack) slack_c = slack;
calc_c_slack=1;
/* printf(" Column Bitmaps being saved: "); */
for( i=0; i < u; i++ ) { /* save the entries in the cols */
col1[i] = bitmap1[i];
col2[i] = bitmap2[i];
/* printf(" %ld-%ld",bitmap1[i],bitmap2[i]); */
}
/* printf("\n"); */
for( i=1; i <= stopper; i++ ) { /* save the valid combos of cols */
prodc[i] = proda[i];
for( r=1; r <= rows; r++ )
col3[r][i] = saved[r][i];
}
bestsoln = factorial;
for( r=1; r <= stopper_r; r++ ) {
for( c=1; c <= stopper_c; c++ ) {
/* Print routines for debugging*/ /*
printf(" testing %d %d \n",r,c);
printf(" row bitmap = %ld \n",row1[row3[1][r]]);
printf(" col bitmap = %ld \n",col1[col3[1][c]]);
*/
if( !( (row1[row3[1][r]]-1) & col1[col3[1][c]] ) ) {
if( !( (row2[row3[1][r]] ) & col2[col3[1][c]] ) ) {
bestsoln = bestsoln < prodr[r]+prodc[c] ? bestsoln :
prodr[r]+prodc[c];
soln=1;
/* The solutions get printed here in bitmap format */ /*
printf(" Solution Possible for '1' entry ... ");
printf("\n Row bitmaps= ");
for ( i=1; i <= cols; i++ )
printf(" %ld-%ld",row1[row3[i][r]],row2[row3[i][r]]);
printf("\n Col bitmaps= ");
for ( i=1; i <= rows; i++ )
printf(" %ld-%ld",col1[col3[i][c]],col2[col3[i][c]]);
printf("\n == %.0Lf + %.0Lf =
%.0Lf\n\n",prodr[r],prodc[c],prodr[r]+prodc[c]);
*/
}
}
}
}
if( !soln ) {
slack_r++;
slack_c++;
printf( " Soln not possible, increasing slacks to %d
%d\n",slack_r,slack_c);
if( rows != cols ) {
t = rows;
rows = cols;
cols = t;
}
goto l1;
}
printf(" The best possible solution is %.0Lf\n",bestsoln);
return 1;
}