The 5040 Square

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.

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.

• Out of curiosity, how did you solve it? Was it just by brute force? – Bailey M Sep 10 '15 at 19:58
• @BaileyM I was editing it when you asked. It was strategical guessing, I would say. – Rohcana Sep 10 '15 at 20:14
• There is an error in your strategy description in 2 squares of the bottom right corner. – Sleafar Sep 10 '15 at 20:20
• +1 For another method of construction (and other examples), check out this page. – Set Big O Sep 11 '15 at 0:10

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
• Woah, what? Verified that rows, columns, diagonals, center 2x2, and corner 2x2s all work. – Ben Frankel Sep 10 '15 at 22:05
• I was just trying to get the diagonals to work out, but it appears I stumbled into a multiplicative version of Durer's magic square – Tyler Seacrest Sep 10 '15 at 22:10
• I've found a few other things to multiply to 5040 as well... – Ben Frankel Sep 10 '15 at 22:18
• This isn't a good solution, it doesn't have 42 ;) – Rohcana Sep 10 '15 at 22:20

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);