# 3x3 “Magic Square” of Prime Numbers — Part II

Glad to know the previous puzzle, which was the first puzzle I posted in Puzzling, was warmly welcomed (Thank you!), and an optimal solution was found. Inspired by the comments there, here is the Version $2$ of the puzzle. In fact, most of the things are unchanged. We still have this $3 \times 3$ grid, which $9$ distinct prime numbers $P_1, P_2, ..., P_9$ are to be filled in. And there are $8$ sums: $3$ horizontal, $3$ vertical and $2$ diagonal, and they are named $S_1, S_2, ..., S_8$. All the requirements in the first version still hold here, which mean:

• $P_1, P_2, ..., P_9, S_1, S_2, ..., S_8$ are all distinct prime numbers (i.e. there are totally $17$ different prime numbers).

But this time, one more additional requirement:

• The grand total $P_1 + P_2 + ... + P_9 + S_1 + S_2 + ... + S_8$ also has to be a prime number.

The challenge: To minimize the grand total.

With the additional requirement, some solutions satisfying the previous puzzle do not satisfy this version. And, the optimal solution will be different.

Below is one possible solution I come up with, which has a grand total of $601$, but it is not the optimal solution: Feel free to have a try!

• Whew! This looks even harder. – Rand al'Thor Mar 24 '15 at 10:23
• I wonder if there's some general theorem from number theory that can be used to solve this kind of problem? The Green-Tao theorem comes to mind... – Rand al'Thor Mar 24 '15 at 10:24
• Yes it will be more difficult due to the additional condition. And from the experience of the previous puzzle, seems like a greedy strategy of putting the smallest primes inside the grid, or positioning them to the center or corners, may not always work towards the optimal solution. – LaBird Mar 24 '15 at 10:31

As our friend @KSab said, the best solution ever is 541. There are exactly 16 possible solutions which are shown in the images belown:  • Yes you are right, indeed I also find $16$ optimal solutions in $2$ different configurations (your answer $1$ and $2$), as rotation and flipping of each configuration gets a set of $8$ identical solutions). – LaBird Mar 25 '15 at 7:28

Using a brute force checker I have found a solution of 541

    7  5 17 | 29
11 23  3 | 37
13 19 41 | 73
---------+---
53 31 47 61 | 71


Notice that a simple lower bound would be 499 which is just the sum of the first 17 primes greater than 2; the result above skips only 3 primes (43, 59, 67) which is what makes me doubt there is a more optimal solution.

The brute force searcher searched every combination of the primes up to 67 which should be conclusive, as increasing the value of one of the inner numbers increases the final answer by at least three times as much, making any increase not worth it at that point.

I used the same numbers as used by you
I got the grand total of 529 which is a prime number. (5 + 11 + 3 + 13 + 7 + 59 + 19 + 23 + 17) + (19 + 79 + 59 + 29 + 29 + 37 + 41 + 79 ) = 529

• A few numbers appear twice, note the OP's restriction that the sums must also be distinct from the elements in the square. – KSab Mar 24 '15 at 14:30
• It's difficult to spot and I made the same mistake before I posted the question, but $529$ is not a prime number ($23 \times 23$). – LaBird Mar 25 '15 at 7:30
• @LaBird, ohh sorry, you are right. – Himanshu Mar 25 '15 at 9:16
• $19, 59, 79$ appear twice, but nice try though :) – Mr Pie Nov 18 '17 at 23:04