20
$\begingroup$

During the thinking and analysis of some mathematical problems, I came up with this puzzle:

enter image description here

Just like any magic square, one has to fill in $9$ different numbers $P_1, P_2, \dots P_9$ to a $3 \times 3$ grid. But this time, all the numbers must be different prime numbers. In addition, the $8$ sums ($3$ horizontal, $3$ vertical and $2$ diagonal) must not only be different prime numbers among themselves, but also be different from the $9$ numbers in the grid. In other words, $P_1, P_2, \dots, P_9, S_1, S_2, \dots, S_8$ must be all different prime numbers.

I suppose there are infinitely many solutions, so the challenge is to minimize the sum $S_1 + S_2 + \dots + S_8$. Here is one answer I found:

enter image description here

The total of the $8$ sums is $480$. I believe there are very likely solutions that can beat this total. You are welcome to have a try.

Update (plus Spoiler Alert): It was verified (using computer program) that one of the answers here (the accepted answer) is the optimal solution that cannot be beaten. There are $8$ optimal solutions, but actually they are the same because if you rotate one of the solutions by $90$, $180$ and $270$ degrees, and also horizontally flip each of the resulting grid, you will get all $8$ answers. Hence the "open-ended" tag has been removed.

$\endgroup$
  • $\begingroup$ Your solution is pretty good, using six of the seven smallest odd primes. It may well not be beatable. Great puzzle though. $\endgroup$ – Rand al'Thor Mar 23 '15 at 11:27
  • 1
    $\begingroup$ @randal'thor Thanks. Mathematically speaking, I tried a greedy strategy. Seems to work nicely until the bottom right hand corner, I need to use $59$, and it is not at the best position either (it is involved in $3$ of the $8$ sums). So that's why I think it is possible to beat the $480$ total. $\endgroup$ – LaBird Mar 23 '15 at 11:33
16
$\begingroup$

With a brute force program solver written in C#, I found a solution with sum 366:

    3 11  5 | 19
   37 17 13 | 67
    7 31 23 | 61
   ---------+---
29 47 59 41 | 43

I let the program run until the top left corner was 61, so I'm pretty sure that there are no better solutions, but feel free to look for yourself:

Source code at PasteBin (you might want to change the initial value of recordSum to something bigger than 366 to actually get some results).

$\endgroup$
  • $\begingroup$ A sum of $366$ is amazing, actually I just got $432$ after a few tries. And from this solution, it seems the traditional strategy of putting a very small prime ($3$ or $5$) at the center may not be the best way(?) $\endgroup$ – LaBird Mar 23 '15 at 14:28
  • $\begingroup$ As I said, my program is still running :) It's still trying all those combinations with a 3 in the top left corner at the moment, so there still might be much better solutions with a 3 or 5 in the middle. $\endgroup$ – schnaader Mar 23 '15 at 14:30
  • $\begingroup$ I see, so there may still be more amazing results to come. :) $\endgroup$ – LaBird Mar 23 '15 at 14:32
  • $\begingroup$ Aborted the program, 366 seems to be the best result. Source code posted in case somebody wants to try out more :) $\endgroup$ – schnaader Mar 23 '15 at 15:12
  • 2
    $\begingroup$ I just wrote a program and verified that your answer cannot be beaten. Well done and Congratulations! $\endgroup$ – LaBird Mar 24 '15 at 7:38
5
$\begingroup$

Here's an example that beats the OP's:

  |11  41   7|  59
  |47   3  17|  67
  |13  83   5| 101
  ------------
23 71 127  29   19

I got this by putting the smallest possible number (3) in the most central position (which is involved in four of the eight sums) and then the next smallest numbers (5, 7, 11, 13) in the positions involved in three of the eight sums, so that $S_1+\dots+S_8$ is minimised.

$\endgroup$
  • 1
    $\begingroup$ For your solution, $23$, $29$ and $31$ have appeared in both the grid and one of the sums, which violates one of the rules of the puzzle (see the paragraph below the first picture). Still, a very good tactic by putting the $3$ at the center. I overlooked this and thought it was impossible! $\endgroup$ – LaBird Mar 23 '15 at 11:56
  • $\begingroup$ @LaBird Oops! I've edited now with a solution that meets the rules and still beats yours, extending the strategy of starting with 3 at the centre. $\endgroup$ – Rand al'Thor Mar 23 '15 at 12:14
  • 3
    $\begingroup$ Your updated example sums up to 496, so I think it's not a solution. $\endgroup$ – schnaader Mar 23 '15 at 13:20
  • 1
    $\begingroup$ @randal'thor Don't you mean 3 is involved in four sums, and [5, 7, 11, 13] are involved in three sums? $\endgroup$ – FreeAsInBeer Mar 23 '15 at 14:12
  • $\begingroup$ @FreeAsInBeer Yes; sorry for the mistake. I'll edit. $\endgroup$ – Rand al'Thor Mar 23 '15 at 21:27
4
$\begingroup$

I just came up with a solution summing up a total of 396:

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

In fact there are exactly 8 matrices summing up 396 using primes {3, 5, 7, 11, 13, 17, 19, 29, 37}.

I will be working around on this problem till I can find a better solution but I think the best possible is the one stated by our friend @schnaader

PS: In fact, there are exactly 8 matrices summing up to 366 using primes {3, 5, 7, 11, 13, 17, 23, 31, 37}, just like the one @schnaader showed us!

$\endgroup$
  • 1
    $\begingroup$ Good observation, in fact you will always find that the no. of matrices summing up to a particular number must be a multiple of 8, as you can rotate the matrix 90, 180 and 270 degrees, and also you can horizontally flip each of the resulting matrix, giving the same sums. As for the optimal solution, yes, I just wrote a program and verified that 366 is the best possible. $\endgroup$ – LaBird Mar 24 '15 at 7:36
  • 1
    $\begingroup$ @LaBird Thanks for your observation. One thing: why not make the sum a prime number also? That would be a really interesting challenge don't you think so? $\endgroup$ – Jose Lopez Garcia Mar 24 '15 at 9:00
  • 1
    $\begingroup$ If you mean the sum $S_1 + S_2 + ... + S_8$, it can never be a prime since every $S_i$ is an odd number, and the sum of $8$ odd numbers will always be even (this sum is surely $\gt 2$ so definitely not a prime). But if you aim at the sum $S_1 + S_2 + ... + S_8 + P_1 + P_2 + ... + P_9$, then this looks possible to be a prime and this can be another challenge. For the accepted solution, its $S_1 + S_2 + ... S_8 + P_1 + P_2 + ... + P_9$ is $513$ which is not a prime, so this new challenge is still open! :) $\endgroup$ – LaBird Mar 24 '15 at 9:24
  • 1
    $\begingroup$ Inspired by your comment, I posted a new puzzle for the new challenge: puzzling.stackexchange.com/questions/10868/… . Thanks a lot! $\endgroup$ – LaBird Mar 24 '15 at 10:20
  • $\begingroup$ You are more than welcome, thanks for your great puzzles! $\endgroup$ – Jose Lopez Garcia Mar 24 '15 at 12:19
2
$\begingroup$

Here's my attempt to solve it:

    5   17  7   |  29
    61  3   19  |  83
    13  47  11  |  71
----------------+----
23  79  67  37  |  19

That sums up to 408 which is better than 480

I kept 3(smallest one) in the middle, because the number in the middle affects 4 different sums(vertical middle, horizontal middle and both diagonals), so increasing the middle number by 1 would increase total sum by 4.
Then, because each number on the diagonal also affects 3 other sums(vertical, horizontal and diagonal), I tried to keep those numbers as small as possible.
And as last, I added 4 last numbers(17, 19, 47 and 61) so that all the sums would be prime too.

$\endgroup$
  • 2
    $\begingroup$ Oops. There are 2 19's. $\endgroup$ – the4seasons Mar 23 '15 at 13:47
  • $\begingroup$ @the4seasons oops, didn't notice this $\endgroup$ – Novarg Mar 23 '15 at 13:47
  • $\begingroup$ Good luck on another solution $\endgroup$ – the4seasons Mar 23 '15 at 13:49
2
$\begingroup$

Here's another solution that reaches 480(!)

   |17   79  13|  109
   | 5    3  59|  67
   | 7   19  11|  37
  ------------
23  29  101  83   31
$\endgroup$
1
$\begingroup$

This is more of a comment as opposed to an answer


    5   29  7   |  41
    23  3   17  |  43
    13  11  59  |  83
----------------+----
23  41  43  83  |  67

Hello! I am new to this, but above is what I found. I do not have a computer to find solutions, so I came up with this by hand.

$$\sum_{n = 1}^8 S_n = \boxed{424}$$

The occurrence of $41, 43$ and $83$ is extraordinary in my opinion, which is why I mentioned this result, but perhaps the best result nonetheless would have to be $366$.

$\endgroup$
  • $\begingroup$ Welcome to Puzzling! I thought the sums had to be different, though. $\endgroup$ – boboquack Nov 17 '17 at 1:07
  • $\begingroup$ @boboquack Haha thank you! And yes they all had to be different, but I found this quite a special case. It's unfortunate I do not have a computer to do the magic, but I guess if I had to try and make them all different, I would first swap the positions of $11$ and $29$. $\endgroup$ – user42374 Nov 17 '17 at 1:08
  • $\begingroup$ Dammit, I just noticed the two $23$'s... $\endgroup$ – Feeds Nov 18 '17 at 23:02

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.