7
$\begingroup$

Place the integers 1 to 16 in the sixteen cells of a 4 x 4 board so that the sum of any four numbers in a row or column is a different prime.

$\endgroup$
  • $\begingroup$ Bernardo may be if you add a condition where diagonals must also add to Prime numbers it could be a unique solution?? Not sure it exists $\endgroup$ – DEEM Sep 4 '17 at 22:58
6
$\begingroup$

Here's one solution I found by hand:

  1  2  3  5  = 11
  4  6  8 13  = 31
  7  9 10 15  = 41
 11 12 16 14  = 53
  =  =  =  =
 23 29 37 47 

This is how I found it:

I first worked out which primes to use. I needed to find two disjoint sets of four primes that had an average of 34, the 4x4 magic number. I made a list as follows:

  p    p-34
 11  -23
 13  -21
 17  -17
 19  -15
 23  -11
 29  -5
 31  -3
 --34
 37  +3
 41  +7
 43  +9
 47  +13
 53  +19
 59  +25
 61  +27
Then I made pairs of primes, one pair both below 34 or and one pair above 34, with matching surplus/deficits:
 16) 29+23                 + 41+43 / 37+47
 20) 29+19 / 31+17         + 41+47
 22) 29+17                 + 37+53 / 43+47
 26) 31+11 / 29+13 / 19+23 + 41+53
From these I chose two disjoint sets of 4: 29+23 + 37+47, and 31+11 + 41+53. One set are the row sums, the other the column sums. The order does not matter as you can reorder the rows. Then I made a little excel sheet to keep track of the sums as I placed the 16 numbers.

For completeness, I wrote a computer program and below are all 28 solutions it found. There are three sets of row/column sum primes that can occur.

  1  2  3  5 = 11    1  2  3  5 = 11    1  2  3  5 = 11    1  2  3  5 = 11
  4  6  7 14 = 31    4  7  9 11 = 31    4  6  9 12 = 31    7  4  8 12 = 31
  8  9 11 13 = 41    8  6 12 15 = 41    7  8 10 16 = 41    6 10 11 14 = 41
 10 12 16 15 = 53   10 14 13 16 = 53   11 13 15 14 = 53    9 13 15 16 = 53
  =  =  =  =         =  =  =  =         =  =  =  =         =  =  =  =
 23 29 37 47        23 29 37 47        23 29 37 47        23 29 37 47

  1  2  3  5 = 11    1  2  3  5 = 11    1  2  3  5 = 11    3  1  2  5 = 11
  4  6  8 13 = 31    4  9  7 11 = 31    4  6 13  8 = 31    4  7  9 11 = 31
  7  9 10 15 = 41    8 12  6 15 = 41    7  9 15 10 = 41    6  8 12 15 = 41
 11 12 16 14 = 53   10 14 13 16 = 53   11 12 16 14 = 53   10 13 14 16 = 53
  =  =  =  =         =  =  =  =         =  =  =  =         =  =  =  =
 23 29 37 47        23 37 29 47        23 29 47 37        23 29 37 47


  1  3  6  7 = 17    1  2  6  8 = 17
  2  4  8  9 = 23    3  4  7  9 = 23
  5 10 13 15 = 43    5 11 13 14 = 43
 11 12 14 16 = 53   10 12 15 16 = 53
  =  =  =  =         =  =  =  =
 19 29 41 47        19 29 41 47


  1  3  9 10 = 23    1  3  9 10 = 23    1  3  9 10 = 23    1  2  9 11 = 23
  2  4 11 12 = 29    2  4 11 12 = 29    2  4 11 12 = 29    3  4 10 12 = 29
  6  5 14 16 = 41    8  5 13 15 = 41    6  7 13 15 = 41    5  7 13 16 = 41
  8  7 13 15 = 43    6  7 14 16 = 43    8  5 14 16 = 43    8  6 15 14 = 43
  =  =  =  =         =  =  =  =         =  =  =  =         =  =  =  =
 17 19 47 53        17 19 47 53        17 19 47 53        17 19 47 53

  1  2  9 11 = 23    1  2  9 11 = 23    1  2  9 11 = 23    1  2  9 11 = 23
  3  4 10 12 = 29    3  4 10 12 = 29    3  4 10 12 = 29    3  4 10 12 = 29
  5  7 15 14 = 41    6  8 13 14 = 41    8  6 13 14 = 41    7  5 15 14 = 41
  8  6 13 16 = 43    7  5 15 16 = 43    5  7 15 16 = 43    6  8 13 16 = 43
  =  =  =  =         =  =  =  =         =  =  =  =         =  =  =  =
 17 19 47 53        17 19 47 53        17 19 47 53        17 19 47 53

  1  2  9 11 = 23    2  1  9 11 = 23    2  1  9 11 = 23    2  1  9 11 = 23
  3  4 10 12 = 29    4  3 10 12 = 29    4  3 10 12 = 29    4  3 10 12 = 29
  7  5 13 16 = 41    5  7 15 14 = 41    5  7 13 16 = 41    6  8 13 14 = 41
  6  8 15 14 = 43    6  8 13 16 = 43    6  8 15 14 = 43    5  7 15 16 = 43
  =  =  =  =         =  =  =  =         =  =  =  =         =  =  =  =
 17 19 47 53        17 19 47 53        17 19 47 53        17 19 47 53

  1  3  9 10 = 23    1  3  9 10 = 23    1  3  9 10 = 23    3  1  9 10 = 23
  4  2 11 12 = 29    4  2 11 12 = 29    4  2 11 12 = 29    2  4 11 12 = 29
  5  6 14 16 = 41    7  6 13 15 = 41    5  8 13 15 = 41    5  6 14 16 = 41
  7  8 13 15 = 43    5  8 14 16 = 43    7  6 14 16 = 43    7  8 13 15 = 43
  =  =  =  =         =  =  =  =         =  =  =  =         =  =  =  =
 17 19 47 53        17 19 47 53        17 19 47 53        17 19 47 53

  3  1  9 10 = 23    3  1  9 10 = 23
  2  4 11 12 = 29    2  4 11 12 = 29
  7  6 13 15 = 41    5  8 13 15 = 41
  5  8 14 16 = 43    7  6 14 16 = 43
  =  =  =  =         =  =  =  =
 17 19 47 53        17 19 47 53

By reordering rows or columns it is even possible to let the two diagonals be two other primes, different to the row/column sums. My program found 44 such solutions. Here is just one:

             /31
  3  7  1  6 = 17
 10 15  5 13 = 43
 12 16 11 14 = 53
  4  9  2  8 = 23
  =  =  =  = \
 29 47 19 41  37

And finally, here are solutions for 5x5, 6x6, 7x7 squares:

   1  2  3  4  7  = 17
   5  6  8  9 13  = 41
  10 11 12 14 20  = 67
  15 24 17 25 16  = 97
  22 18 19 21 23  = 103
   =  =  =  =  =
  53 61 59 73 79
 
   1   2   3   4   5   8  = 23
   6   7   9  10  11  16  = 59
  12  13  14  15  17  18  = 89
  19  20  21  22  23  26  = 131
  24  27  29  28  32  33  = 173
  35  34  31  30  25  36  = 191
   =   =   =   =   =   =
  97 103 107 109 113 137
 
   1   2   3   4   5   6   8  = 29
   7   9  10  11  12  13  17  = 79
  14  15  16  18  19  20  25  = 127
  21  22  23  24  26  27  30  = 173
  28  29  31  32  33  34  36  = 223
  35  37  38  42  39  49  41  = 281
  45  43  46  48  47  44  40  = 313
   =   =   =   =   =   =   =
 151 157 167 179 181 193 197

$\endgroup$
  • $\begingroup$ Any other solutions? $\endgroup$ – Bernardo Recamán Santos Sep 4 '17 at 13:27
  • $\begingroup$ What about the 5 x 5 case with integers 1 to 25? $\endgroup$ – Bernardo Recamán Santos Sep 4 '17 at 13:28
  • $\begingroup$ I don't know if there are other sets of primes, Once I found the ones I used I didn't look further. There are other solutions to the square, e.g. swap 3 and 5 as well as 14 and 16, but probably not very many. $\endgroup$ – Jaap Scherphuis Sep 4 '17 at 14:12
  • $\begingroup$ Interestingly, this also has a prime sum on the diagonal. Maybe requiring that makes the puzzle unique? $\endgroup$ – The Great Duck Sep 4 '17 at 19:15
  • 1
    $\begingroup$ @Typhon: According to my computer program there are 44 solutions where the rows, columns, and main diagonals add up to distinct prime numbers. I have edited my answer to show one of them. $\endgroup$ – Jaap Scherphuis Sep 5 '17 at 12:43
2
$\begingroup$

There are too many solutions, so I have showns a few of them then stopped:

1:

$\begin{bmatrix} 1& 2 &7 &3 \\ 6 & 11 &9 &5 \\ 8 &12 &16 &13 \\ 10 & 4 & 15 &14 \end{bmatrix}$

2:

$\begin{bmatrix} 1& 2 &7 &3 \\ 6 & 11 &9 &5 \\ 8 &12 &16 &13 \\ 14 & 10 & 15 &4 \end{bmatrix}$

3:

$\begin{bmatrix} 2& 5 &1 &7 \\ 3 & 6 &9 &11 \\ 8 &12 &16 &13 \\ 10 & 14 & 15 &4 \end{bmatrix}$

4:

$\begin{bmatrix} 2& 5 &7 &1 \\ 3 & 6 &9 &11 \\ 8 &12 &16 &13 \\ 4 & 14 & 15 &10 \end{bmatrix}$

5:

$\begin{bmatrix} 3& 1 &2 &7 \\ 4 & 5 &9 &11 \\ 6 &12 &8 &15 \\ 10 & 13 & 16 &14 \end{bmatrix}$

6:

$\begin{bmatrix} 3& 1 &2 &7 \\ 4 & 9 &5 &11 \\ 6 &12 &8 &15 \\ 10 & 13 & 16 &14 \end{bmatrix}$

7:

$\begin{bmatrix} 1& 2 &4 &6 \\ 3 & 5 &7 &8 \\ 10 &9 &12 &16 \\ 11 & 15 & 14 &13 \end{bmatrix}$

8:

$\begin{bmatrix} 1& 2 &4 &6 \\ 3 & 5 &7 &8 \\ 12 &9 &10 &16 \\ 13 & 15 & 14 &11 \end{bmatrix}$

9:

$\begin{bmatrix} 1& 2 &4 &6 \\ 3 & 5 &7 &8 \\ 12 &9 &10 &16 \\ 13 & 15 & 14 &11 \end{bmatrix}$

10:

$\begin{bmatrix} 1& 2 &4 &8 \\ 3 & 6 &11 &5 \\ 9 &15 &7 &12 \\ 10 & 14 & 13 &16 \end{bmatrix}$

10:

$\begin{bmatrix} 1& 2 &5 &3 \\ 4 & 8 &7 &6 \\ 11 &12 &14 &10 \\ 13 & 9 & 15 &16 \end{bmatrix}$

I think there are too many solutions, so I stopped :)

$\endgroup$
  • $\begingroup$ Hmm. The solution I found is not among these, as none of them have a row or column with 1+2+3+5=11. $\endgroup$ – Jaap Scherphuis Sep 4 '17 at 15:17
  • $\begingroup$ @JaapScherphuis still updating :) $\endgroup$ – Oray Sep 4 '17 at 15:19
  • $\begingroup$ The last two of your solutions have a row sum of 25, which is not a prime. I get only 28 solutions, excluding row/column permutations. $\endgroup$ – Jaap Scherphuis Sep 4 '17 at 22:13
  • $\begingroup$ Oray is there a solution where diagonals also add up to Prime numbers? That could be unique $\endgroup$ – DEEM Sep 4 '17 at 22:55
  • $\begingroup$ @DeepakMahulikar According to my computer program there are 44 solutions where the rows, columns, and diagonals add up to distinct prime numbers. One of them is shown in my answer. $\endgroup$ – Jaap Scherphuis Sep 5 '17 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.