Maximize the prime sums in a table

The entries of a $3×3$ table are integers from $1$ to $9$, and each number appears exactly once. Consider the row, column, and diagonal sums of numbers in the table. Find the maximum number of these eight sums that can be prime numbers. How can I start with the problem? It is not a combinatorics problem, though looks like one.

• Well there are only six primes between 6 and 24. And only one way to get 7 (1+2+4) and one way to get 23 (6+8+9). That shouldn't leave too many possible combinations. – Gregory Grant Mar 2 '15 at 6:28
• I can't think of any reason why the maximal configuration should have those two primes as a row, column, or diagonal sum. – William Stagner Mar 2 '15 at 6:30
• @GregoryGrant: But primes can appear more than once (and must, in a maximal configuration). – Charles Mar 2 '15 at 15:08

Brute force solution:

a(n)=my(v=numtoperm(9,n));vecsum(apply(isprime,[v[1]+v[2]+v[3],v[4]+v[5]+v[6],v[7]+v[8]+v[9],v[1]+v[4]+v[7],v[2]+v[5]+v[8],v[3]+v[6]+v[9],v[1]+v[5]+v[9],v[3]+v[5]+v[7]]))
r=0;for(n=0,9!-1,t=a(n);if(t>r,r=t;print(r" "numtoperm(9,n))))


This takes half a second on my machine.

There are 96 solutions (plus their reflections and rotations) for which 7 of the sums are prime. These are: $$\left\{\begin{array}{ccc} 1&2&4\\ 5&8&6\\ 7&3&9 \end{array},\qquad \begin{array}{ccc} 1&2&4\\ 5&8&6\\ 7&9&3 \end{array},\qquad \begin{array}{ccc} 1&2&8\\ 7&6&4\\ 3&9&5 \end{array},\qquad \begin{array}{ccc} 1&2&8\\ 7&6&4\\ 9&3&5 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 5&2&6\\ 7&8&4 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 5&8&6\\ 7&2&4 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 7&4&2\\ 5&6&8 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 7&4&8\\ 5&6&2 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&2&8\\ 3&5&9 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&2&8\\ 9&5&3 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&8&2\\ 3&5&9 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&8&2\\ 9&5&3 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 8&2&3\\ 4&6&9 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 8&2&9\\ 4&6&3 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 9&2&8\\ 3&6&4 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 9&8&2\\ 3&6&4 \end{array},\qquad \begin{array}{ccc} 1&7&3\\ 8&6&9\\ 2&4&5 \end{array},\qquad \begin{array}{ccc} 1&7&5\\ 9&4&6\\ 3&2&8 \end{array},\qquad \begin{array}{ccc} 1&7&5\\ 9&4&6\\ 3&8&2 \end{array},\qquad \begin{array}{ccc} 1&7&9\\ 8&6&3\\ 2&4&5 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&5&9\\ 8&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&7&5\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&7&9\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&7&9\\ 8&5&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&9&5\\ 6&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&9&7\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 5&3&7\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 5&9&7\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&3&5\\ 6&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&3&7\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&5&3\\ 8&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&7&3\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&7&3\\ 8&5&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&7&5\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 3&5&9\\ 8&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 5&3&9\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 5&9&3\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 9&5&3\\ 8&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 3&5&9\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 3&5&9\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 3&9&5\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 5&3&9\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 5&9&3\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 9&3&5\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 9&5&3\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 9&5&3\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&3&4\\ 5&1&7\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&3&4\\ 5&7&1\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&3&4\\ 7&5&1\\ 8&9&6 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 5&1&9\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 5&7&9\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&1&5\\ 4&9&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&1&9\\ 4&5&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&5&1\\ 8&9&4 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&9&1\\ 4&5&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&9&1\\ 8&5&4 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&9&5\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 5&1&7\\ 6&9&4 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 5&7&1\\ 6&9&4 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 7&1&5\\ 4&9&6 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 7&5&1\\ 4&9&6 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 7&5&1\\ 6&9&4 \end{array},\qquad \begin{array}{ccc} 2&4&5\\ 8&6&3\\ 7&1&9 \end{array},\qquad \begin{array}{ccc} 2&4&5\\ 8&6&9\\ 7&1&3 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&3&1\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&3&1\\ 8&9&6 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&9&1\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&9&1\\ 8&3&6 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 9&1&7\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 9&7&1\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 7&3&9\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 7&9&3\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&1&3\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&1&3\\ 8&7&4 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&7&3\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&7&3\\ 8&1&4 \end{array},\qquad \begin{array}{ccc} 2&6&5\\ 8&4&1\\ 3&9&7 \end{array},\qquad \begin{array}{ccc} 2&6&5\\ 8&4&1\\ 9&3&7 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&1&3\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&1&3\\ 8&5&6 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&1&5\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&3&1\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&3&5\\ 6&1&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&5&3\\ 8&1&6 \end{array},\qquad \begin{array}{ccc} 2&7&6\\ 9&5&3\\ 8&1&4 \end{array},\qquad \begin{array}{ccc} 2&7&8\\ 9&3&5\\ 6&1&4 \end{array},\qquad \begin{array}{ccc} 2&7&8\\ 9&5&3\\ 4&1&6 \end{array},\qquad \begin{array}{ccc} 2&7&8\\ 9&5&3\\ 6&1&4 \end{array},\qquad \begin{array}{ccc} 3&1&7\\ 5&2&4\\ 9&8&6 \end{array},\qquad \begin{array}{ccc} 3&1&7\\ 5&8&4\\ 9&2&6 \end{array},\qquad \begin{array}{ccc} 3&1&7\\ 9&6&2\\ 5&4&8 \end{array},\qquad \begin{array}{ccc} 3&2&6\\ 5&8&4\\ 9&1&7 \end{array},\qquad \begin{array}{ccc} 3&2&8\\ 9&4&6\\ 7&1&5 \end{array},\qquad \begin{array}{ccc} 3&5&9\\ 8&2&1\\ 6&4&7 \end{array},\qquad \begin{array}{ccc} 5&1&7\\ 6&4&3\\ 8&2&9 \end{array},\qquad \begin{array}{ccc} 5&3&9\\ 4&6&1\\ 8&2&7 \end{array}\right\}$$

• Your middle column is not prime in any case. Therefore the answer should be 7, shouldn't it. – user167045 Mar 2 '15 at 15:30
• @Garvil: Good catch! There was a typo in my program, it was checking $v_2+v_6+v_8$ instead of $v_2+v_5+v_8$. I fixed it. – Charles Mar 2 '15 at 15:58
• How about determining the maximum number of different primes that can be obtained? Just for fun. I think it's five. – Gregory Grant Mar 3 '15 at 15:30
• @GregoryGrant: Yes, it's five. The possibilities for the primes are {{7, 11, 13, 17, 19}, {7, 11, 13, 17, 23}, {7, 13, 17, 19, 23}, {11, 13, 17, 19, 23}}, and there are 176 configurations (22 + symmetries) which achieve one of these. – Charles Mar 3 '15 at 15:42

Well we can set an upper-bound and also constrain the solution space with the following:

Any sum S of three distinct integers must be >= 6, and <= 7+8+9=24 The only primes between 6..24 are 7,11,13,17,19,23 i.e. {6k + 1 or 5}

In order for S >= 6 to be prime, consider its residues both mod 2,3 and 6 must necessarily be:

• mod 2, S == 1
• mod 3, S == 1 or 2
• mod 6, S == 1 or 5

Then rewrite A:{1..9} as b = a-6: B:{-5,-4,-3,-2,-1,0,1,2,3} Then S will be prime if S == -7,-5,-1,1,5 mod 6

Calling the integers A = (a_1, a_2... a_9),

• mod 2, A is five ones and four zeros
• mod 3, A is three zeros, three ones, three twos
• mod 6, A is (1..5,0..3)

So, how do we choose the placement of S mod 2 and S mod 3 in order to maximize the number of sums which are both odd (mod 2) and residue 1 or 2 (mod 3).

• mod 2, we can make all 3+3+2 of the diagonal+row+column sums odd with the following pattern: one row and one column contain three odd numbers, the other two rows and columns one each

.e.g. one of 3x3 such possible arrangements mod-2 is:

0 1 0
1 1 1
0 1 0