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.

***

On June 23, Michael Hürter wrote:

For Q2, k = 6, there exists no solution (other k = 2 + 4 * n, n >= 1, are the same).

Why ?

At least one of the sums is even.

To prove this we can show that the corresponding linear equation system modulo 2 has no solution.

The following (k^2) * (4*k) Matrix M of this system has k entries in each row:
to The following (k^2) * (4*k) Matrix M of this system has k entries with value 1 in each row:

M = {
{1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
, {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}
, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1}
, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}
, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0}
, {0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}
, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}
, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1}
, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0}
, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}
, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0}
, {0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0}
, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}
, {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1}
, {0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0}
, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}
, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}
, {0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}
, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}
}

Define vector b of length (4*k):

b = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

Then M * x = b has no solution modulo 2.
I checked this for k = 6, ..., 74 with a program.

***

On June 28, 2018. Michael Hürter wrote again:

I have the following new solutions for Q2:

k = 5, score = 389
17 8 12 9 21
48 24 4 13 42
30 5 18 3 15
1 14 19 20 25
7 2 6 16 10

Unique primes: 103 53 59 61 113 67 131 71 79 41 73 83 97 107 29 89 47 43 101 109

k = 7, score = 1341

10 13 9 65 54 2 28
21 3 37 42 33 67 26
22 30 36 23 31 19 12
14 5 32 24 29 39 20
60 40 18 46 34 4 69
6 15 8 7 25 17 35
16 1 11 44 51 45 43

Unique primes: 149 107 151 251 257 193 233 181 229 173 163 271 113 211 199 139 137 127 283 277 179 167 157 197 223 239 131 227

k = 8, score = 2178

41 52 20 54 50 43 16 35
44 5 46 9 48 51 22 38
6 23 13 79 24 31 25 26
73 19 40 39 29 34 80 33
59 4 10 61 47 56 49 67
30 36 17 28 74 18 53 1
2 42 8 32 11 27 7 68
14 12 37 15 66 21 55 3

Unique primes: 269 193 191 317 349 281 307 271 311 263 227 347 353 257 197 223 251 233 401 157 409 179 367 181 173 397 151 389 277 283 149 359

k = 13, score = 14563

21 71 174 134 139 96 4 28 109 40 141 15 199
129 5 24 53 56 27 81 26 14 92 22 7 137
60 30 90 64 3 42 51 157 63 37 99 49 82
41 79 17 85 136 101 148 120 6 59 23 166 170
16 156 128 75 1 182 10 70 32 152 95 38 76
116 47 149 86 97 44 105 57 34 133 114 31 74
106 73 110 58 11 115 19 160 36 50 25 169 65
54 142 112 83 135 118 18 61 119 195 163 127 126
91 100 84 93 43 132 167 62 162 140 108 87 104
8 9 67 46 125 131 117 130 144 168 98 35 145
29 45 55 68 113 173 72 69 111 12 52 146 124
20 39 89 181 138 33 78 102 151 80 122 88 158
48 13 94 77 66 107 121 159 2 161 155 103 123

Unique primes: 739 809 1193 1103 1063 1301 991 1201 983 1319 1217 1061 1583 1171 673 827 1151 1031 1087 997 1453 1373 1223 1069 1279 1229 821 1021 1459 1297 1019 1321 1307 1033 911 1291 1283 947 853 919 1451 929 1091 977 1303 877 859 1471 887 1399 1277 1123

***

 Records   |  Conjectures  |  Problems  |  Puzzles