7
$\begingroup$

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.

enter image description here

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:

enter image description here

Feel free to have a try!

Improve this question
$\endgroup$
3
  • $\begingroup$ Whew! This looks even harder. $\endgroup$
    – Rand al'Thor
    Mar 24, 2015 at 10:23
  • $\begingroup$ 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... $\endgroup$
    – Rand al'Thor
    Mar 24, 2015 at 10:24
  • $\begingroup$ 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. $\endgroup$
    – LaBird
    Mar 24, 2015 at 10:31

3 Answers 3

Reset to default
3
$\begingroup$

As our friend @KSab said, the best solution ever is 541. There are exactly 16 possible solutions which are shown in the images belown:

Solutions 1 to 8

Solutions 9 to 16

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – LaBird
    Mar 25, 2015 at 7:28
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

I used the same numbers as used by you
I got the grand total of 529 which is a prime number.

enter image description here

(5 + 11 + 3 + 13 + 7 + 59 + 19 + 23 + 17) + (19 + 79 + 59 + 29 + 29 + 37 + 41 + 79 ) = 529

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ A few numbers appear twice, note the OP's restriction that the sums must also be distinct from the elements in the square. $\endgroup$
    – KSab
    Mar 24, 2015 at 14:30
  • 2
    $\begingroup$ 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$). $\endgroup$
    – LaBird
    Mar 25, 2015 at 7:30
  • $\begingroup$ @LaBird, ohh sorry, you are right. $\endgroup$
    – Himanshu
    Mar 25, 2015 at 9:16
  • $\begingroup$ $19, 59, 79$ appear twice, but nice try though :) $\endgroup$
    – Mr Pie
    Nov 18, 2017 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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