Problems & Puzzles: Collection 20th

Coll.20th-003. Primeful Heterosquares

On March 12, 2018, Dmitry Kamenetsky posed the following puzzle:

Place distinct positive integers on a NxN grid, such that their sum is minimal and:

1. The sums of all rows, all Columns and two main diagonals are distinct primes

or

2. The sums of all rows, all Columns and all broken diagonals (diagonals that wrap around) are distinct primes

Examples sent by Dmitry:

1. TWO DIAGONALS
 
N=3, score=57
8 5 4 
7 3 1 
16 11 2 
Unique primes: 7 11 13 17 19 23 29 31
2. ALL DIAGONALS
 
N=3, score=129
13 5 49 
7 27 9 
3 15 1 
Unique primes: 13 17 19 23 37 41 43 47 59 67 71 79
 
Q. Sent your minimal solutions for K>3 as large as you can.

 

Contributions came from Claudio Meller, Michael Hürter, Emmanuel Vantieghem and Dmitry Kamenetski.

***

Claudio sent two solutions for N=4:

 

***

Michael wrote:

Q1.
 
For k > 3, 1 .. k^2 can be placed and the minimal score is k^2/2*(k^2+1).
 
k = 4, score = 136
15 16 10 12
6 8 1 2
7 5 3 4
13 14 9 11
Unique primes: 53 17 19 47 41 43 23 29 37 31
 
k = 5, score = 325
18 25 16 20 4
23 15 10 19 12
13 24 17 21 14
9 11 3 6 2
8 22 7 1 5
Unique primes: 83 79 89 31 43 71 97 53 67 37 61 59
 
k = 7, score = 1225
27 5 29 34 45 9 44
35 20 16 10 46 33 31
19 6 14 32 30 12 38
39 22 26 15 36 48 47
18 13 25 21 23 8 49
41 24 28 42 40 17 37
2 7 1 43 3 4 11
Unique primes: 193 191 151 233 157 229 71 181 97 139 197 223 131 257 127 173
 
For k = 100, my program runs few minutes.
 
Q2.
 
k = 4, score = 234
2 18 7 16
32 14 12 43
3 15 10 39
4 6 8 5
Unique primes: 43 101 67 23 41 53 37 103 47 61 97 29 31 71 59 73
 
k = 5, score = 525
12 37 3 46 5
4 13 7 9 28
24 20 11 39 33
30 47 2 41 17
1 32 36 22 6
Unique primes: 103 61 127 137 97 71 149 59 157 89 73 113 151 79 109 83 53 181 107 101

***

Emmanuel wrote:

4x4, two diagonals :
   13, 14, 3,  17
   20,  6,  5,  12
   18,  7,  1,  15
    8,   4,  2,   9
Sum : 154
Unique primes : 11, 23, 29, 31, 37, 41, 43, 47, 53, 59

 
4x4, all diagonals :
   1,  2,   3,   5
  26, 12, 17, 6
  25, 14,  9, 23
  37, 15,  8,  7 
Sum : 210
Unique primes : 11, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 89

 
5x5, two diagonals
   1, 2, 3, 4, 7
   5, 6, 8, 9, 13
   12, 16, 11, 18, 26
   30, 19, 14, 10, 28
   25, 24, 23, 20, 15
Sum : 349
Unique primes : 17, 41, 43, 59, 61, 67, 71, 73, 83, 89, 101, 107

 
5x5, all diagonals
   1, 2, 3, 4, 7
   5, 6, 8, 9, 13
   12, 10, 17, 37, 55
   15, 20, 11, 53, 28
   14, 21, 22, 4, 36
Sum : 413
Unique primes :17, 37, 41, 47, 53, 59, 61, 67, 71, 73, 83, 89, 97, 103, 107, 113, 127, 131, 137, 139

***

Dmitry sent the following solutions:

For Q1: N=4 to 9

For Q2: N=4 to 13, except N=6 and 10.

I will show today only the solutions for N=4 because we do not want to spoil the work that other puzzlers could be making.

Question 1:
 
N=4, sum=136
12 14 11 16 
10 13 9 15 
3 8 1 7 
4 6 2 5 
Unique primes: 17 19 23 29 31 37 41 43 47 53
 

Question 2:
 

N=4, sum=178
4 19 8 16 
15 7 17 2 
3 11 1 14 
9 6 41 5 
Unique primes: 13 17 19 23 29 31 37 41 43 47 53 59 61 67 83 89

***

Here are the omitted results by Dmitry:

Solutions for Q1.

N=5, sum=325
2 3 21 7 20 
9 6 10 15 19 
12 11 18 17 13 
16 22 25 24 14 
8 1 5 4 23 
Unique primes: 41 43 47 53 59 67 71 73 79 83 89 101

 

 
N=6, sum=666
1 22 10 9 2 27 
30 18 19 16 31 23 
34 5 13 3 24 4 
6 36 12 32 26 15 
25 33 11 29 20 21 
7 35 14 8 28 17 
Unique primes: 71 79 83 97 101 103 107 109 113 127 131 137 139 149

 

 
N=7, sum=1225
2 15 11 9 23 5 24 
32 20 38 13 6 40 42 
7 33 10 30 45 19 35 
14 25 46 47 16 18 31 
29 41 21 8 1 37 36 
22 49 4 34 12 3 39 
43 28 27 26 48 17 44 
Unique primes: 89 127 139 149 151 157 163 167 173 179 191 197 211 233 251 269

 
N=8, sum=2080
21 37 43 5 20 38 18 45 
64 13 61 29 53 50 55 54 
4 7 6 19 10 25 35 33 
49 63 17 30 58 52 39 23 
27 22 24 28 3 2 57 36 
26 9 15 46 41 14 16 62 
48 59 51 44 1 60 8 12 
32 31 34 56 47 40 11 42 
Unique primes: 137 139 199 227 229 233 239 241 251 257 271 281 283 293 307 317 331 379

 
N=9, sum=3321
6 19 42 55 58 17 5 51 16 
3 35 14 67 57 26 12 18 75 
46 62 81 33 45 63 10 74 65 
71 66 21 59 50 44 27 24 77 
38 9 25 30 15 76 40 41 7 
52 8 70 32 60 79 22 13 31 
11 23 54 47 64 69 61 29 43 
37 1 72 28 36 49 2 53 39 
73 48 4 80 34 20 78 56 68 
Unique primes: 257 263 269 271 281 307 317 337 359 367 383 401 419 421 431 439 443 457 461 479
 

Question 2:

N=4, sum=178
 
Alternative solution
sum=178
1 19 5 22 
13 4 21 3 
8 37 6 10 
9 7 11 2 
Unique primes: 13 17 19 23 29 31 37 41 43 47 53 59 61 67 83 89

 

 
N=5, sum=395
8 12 36 1 22 
19 10 15 11 18 
28 5 17 14 39 
24 7 16 6 56 
4 3 13 9 2 
Unique primes: 31 37 41 43 47 59 61 67 71 73 79 83 89 97 101 103 109 113 137 139

 

 
N=6. I believe this one is not possible, but I haven't proved it

 
N=7, sum=1457
4 33 28 16 49 26 17 
58 6 25 24 29 48 51 
15 53 52 18 35 11 55 
43 37 31 3 27 47 9 
57 13 89 8 77 32 1 
2 23 22 7 38 5 10 
12 14 36 21 56 64 20 
Unique primes: 97 107 137 139 149 151 157 163 167 173 179 181 191 197 199 223 227 233 239 241 251 269 277 281 283 293 311 313

 
N=8, sum=2262
14 21 11 8 16 13 17 49 
66 30 19 9 51 80 63 71 
25 50 36 64 26 75 60 47 
18 20 53 32 33 41 52 68 
31 5 2 77 10 40 57 29 
44 15 22 27 46 4 45 38 
12 59 55 6 34 3 42 28 
61 69 35 54 7 1 23 43 
Unique primes: 149 179 181 193 197 211 223 227 233 239 241 251 257 263 269 271 277 281 283 293 311 313 317 347 353 359 367 373 379 383 389 439

 
N=9, sum=3773
37 23 103 67 63 71 68 39 8 
13 101 42 2 10 19 92 85 93 
58 41 47 17 6 20 21 22 61 
55 28 18 15 31 16 11 25 72 
76 38 106 57 46 86 65 64 135 
34 3 24 36 7 87 96 1 49 
51 40 12 60 43 48 53 75 27 
33 9 121 4 66 82 35 54 29 
44 30 26 5 45 112 62 14 83 
Unique primes: 241 263 271 277 283 293 307 311 313 317 331 337 347 379 397 401 409 419 421 433 443 457 463 467 479 487 499 503 521 523 541 547 557 569 613 673

 
N=10. I believe this one is not possible, but I haven't proved it

 
N=11, sum=8197
57 63 4 109 32 106 3 12 53 65 5 
54 64 47 89 121 84 9 127 2 159 55 
104 148 154 132 152 90 60 91 1 99 30 
58 35 25 136 67 23 93 74 86 36 94 
113 128 8 98 145 77 101 70 111 80 40 
13 75 51 18 79 85 46 66 116 6 38 
162 24 21 43 44 42 29 59 103 48 102 
96 26 71 143 7 11 39 37 69 20 88 
92 107 81 105 33 68 82 16 112 133 10 
17 175 62 41 28 108 22 49 118 78 45 
115 14 95 27 31 15 19 72 52 163 56 
Unique primes: 463 503 509 523 563 569 587 593 599 607 619 631 643 659 673 677 683 691 701 709 719 727 739 743 751 761 769 773 787 811 823 827 839 853 859 881 887 941 953 971 983 1031 1061 1097

 
N=12, sum=11264
248 76 25 31 14 98 89 114 2 34 1 155 
105 11 53 65 84 80 176 33 30 96 131 43 
125 10 92 61 69 112 45 60 5 82 73 119 
83 37 8 101 159 110 49 124 21 97 193 169 
55 100 12 77 19 42 67 74 47 86 62 120 
151 162 52 7 58 121 71 111 87 185 72 46 
66 85 88 63 23 22 54 115 35 6 78 38 
57 59 109 93 116 36 64 99 32 4 118 190 
41 15 127 133 102 128 157 9 163 27 91 104 
79 95 39 68 194 13 16 141 94 138 143 29 
113 3 28 90 70 40 129 48 134 51 167 56 
106 144 26 20 75 189 50 81 107 17 24 18 
Unique primes: 547 617 619 659 673 677 733 757 761 773 797 809 823 827 853 857 863 877 883 887 907 911 929 941 947 953 967 971 977 983 991 997 1009 1013 1049 1051 1063 1087 1097 1123 1151 1153 1213 1229 1231 1237 1283 1301

 
N=13, sum=15237
132 5 50 4 72 111 19 157 150 141 49 162 251 
97 174 151 147 156 100 80 43 20 122 203 90 70 
108 120 221 134 166 114 74 158 301 82 172 88 15 
144 161 62 154 63 131 34 44 3 46 18 61 56 
140 96 133 93 60 22 119 36 104 29 48 40 89 
77 245 23 65 71 128 1 69 16 83 103 109 127 
68 242 31 116 86 47 106 126 59 58 33 193 94 
153 39 41 30 55 57 125 27 149 102 87 187 135 
26 53 7 51 130 17 78 28 54 171 38 75 101 
25 84 32 115 142 107 76 24 117 91 113 118 173 
148 14 143 81 137 177 52 13 129 2 155 79 191 
66 95 42 21 6 64 98 37 168 9 11 92 10 
45 105 35 8 145 12 67 121 139 85 99 73 159 
Unique primes: 719 773 829 883 887 911 929 941 947 967 971 977 991 997 1009 1019 1021 1031 1033 1063 1069 1087 1091 1093 1097 1117 1129 1181 1187 1201 1217 1229 1231 1259 1279 1289 1303 1321 1361 1367 1399 1409 1423 1433 1447 1453 1471 1499 1543 1553 1559 1753

***

Michael Hürter wrote on June 22, 2018:


For Q2, k = 2 + 4 * n, n >= 1, there is no solution...

I checked this assumption for k = 6 to k = 74 with a program, so this is no proof,
there could be errors in my program.

***

 

Records   |  Conjectures  |  Problems  |  Puzzles