The 5040 Square

Question

Fill a $4\times4$ grid with positive integers so that:

• Every cell has a different integer
• The product of the numbers in each row is $5040$, and similarly for the columns

Source: This was an NPR weekly listener challenge, aired on 2005-10-09. See here.

Answer 1

A possible solution is:

10   8    3  21
12  15   14   2
 1   7   30  24
42   6    4   5

Strategy

$$5040=2^4 \times 3^2 \times 5 \times 7$$

First I decided where to put the multiples of $7$ and $5$. Then I multiplied proper exponents of $2$ and $3$ to each cell. I started with:

5 1 1 7
1 5 7 1
1 7 5 1
7 1 1 5

This formation ensures that the number of cells without a $5$ or $7$ stays minimum. There are other such formations. But this is the most simple.

Now, There are eight $1$'s, four each of $5$ and$7$. When adding exponents of $3$ my strategy was to half each number of repeatation. A simple pattern was:

1 1 3 3
3 3 1 1
1 1 3 3
3 3 1 1

Multiplying by this grid the previous one, we have:

 5  1  3 21
 3 15  7  1
 1  7 15  3
21  3  1  5

Now the repeatation pattern was like this (same color represents same powers of $3$, $5$, $7$ in factorization):

For any two cells with the same color I had to differentiate them by multiplying different powers of $2$. Note the red and yellow cells. There are four of each. Hence I needed at least four different powers of $2$, $2^4$ couldn't be chosen because putting $2^4$ in a red or yellow cell, forces two cells of the opposite color to have same powers of $2$, hence be same. So, the four red and yellow cells had to be multiplied with $2^0, 2^1, 2^2,2^3$ A bit of fiddling led to the pattern:

2 8 1 1
4 1 2 2
1 1 2 8
2 2 4 1

Multiplying by this grid, we get the desired solution.

Answer 2

Another solution (with diagonals as bonus):

10    4    6   21
18    7   20    2
28   12    3    5
 1   15   14   24

Things that multiply to 5040:

• each of the four rows
• each of the four columns
• each of two diagonals
• four center cells
• four corner cells
• two middle cells of the top row two middle cells of bottom row
• two middle cells of the rightmost column and two middle cells of the leftmost column
• each of the four corner 2x2 grids

Answer 3

After unsuccessful manual fiddling with the prime factors I decided to write a program, unfortunately not fast enough. Here it is anyway. It should print all possible solutions, but will contain duplicates. And I have no idea how long it takes to run, there are many solutions.

public class Main {
    private static final int SIZE = 4;
    private static final int[] FACTORS = new int[] {2, 2, 2, 2, 3, 3, 5, 7};

    private static final ArrayList<int[]> perms = new ArrayList<>();

    private static void generateGrids(int depth, int[] grid) {
        if (depth < FACTORS.length) {
            for (int[] perm : perms) {
                for (int i = 0; i < SIZE; ++ i) {
                    grid[i * SIZE + perm[i]] *= FACTORS[depth];
                }
                generateGrids(depth + 1, grid);
                for (int i = 0; i < SIZE; ++ i) {
                    grid[i * SIZE + perm[i]] /= FACTORS[depth];
                }
            }
        } else {
            int[] tmp = new int[SIZE * SIZE];
            System.arraycopy(grid, 0, tmp, 0, tmp.length);
            Arrays.sort(tmp);
            for (int i = 0; i < tmp.length - 1; ++ i) {
                if (tmp[i] == tmp[i + 1]) {
                    return;
                }
            }
            System.out.println(Arrays.toString(grid));
        }
    }

    private static void generatePerms(int depth, int[] perm) {
        outer:
        for (int i = 0; i < SIZE; ++i) {
            for (int j = 0; j < depth; j++) {
                if (i == perm[j]) {
                    continue outer;
                }
            }
            perm[depth] = i;
            if (depth < SIZE - 1) {
                generatePerms(depth + 1, perm);
            } else {
                int[] tmp = new int[SIZE];
                System.arraycopy(perm, 0, tmp, 0, SIZE);
                perms.add(tmp);
            }
        }
    }

    public static void main(String[] args) {
        generatePerms(0, new int[SIZE]);
        int[] grid = new int[SIZE * SIZE];
        Arrays.fill(grid, 1);
        generateGrids(0, grid);
    }
}