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.
 A: 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

