Problems & Puzzles: Puzzles

Puzzle 120. Primal Squares

A Primal Square (*) is an nxn arrangement of numbers such that every two adjacent - horizontal & vertical, but not diagonal - numbers sum up to a prime number.

Example:

 1 2 5 4 3 8 7 10 9

It's easy to verify that there is no solution for n=3 with consecutive numbers.

Question 1. Can you explain why ?

Otherwise, for every n>3 it appears (this is my conjecture) that always exists at least one solution using the first n2 natural numbers. A 4x4 example sent by Jean-Charles Meyrignac is:

 1 4 7 6 2 9 10 13 11 8 3 16 12 5 14 15

Question 2. Can you develop an algorithm to find at least one of these kind of solutions for any n>3?

Question 3. Using your own algorithm can you produce the solution for n = 10, 20 & 30

Question 3. Jean Charles Meyrignac asks if an (even) Magic Square can be also a Primal Square. In such a case can you produce & send the first example?

A Primal Square is said to satisfy the 'full torus condition'  if is prime the sum of every two symmetric (not necessarily adjacent) cells out of the main diagonals. The mentioned symmetry is respect both the horizontal and the vertical symmetry axis of the square. Obviously the full torus condition can not be satisfied by odd nxn squares.

The 4x4 example sent by Jean-Charles is a Primal Square but does not satisfy the full torus condition because none of the following: 4+5, 7+14, 2+13, 11+16 is prime (of course, is enough only one failure to spoil the full torus condition).

Question 4. Can you find a Primal Square that satisfy the full torus condition for n = 4, 6, 8 & 10?
_______

Note: According to Jean-Charles Meyrignac, these squares were first studied by Fred Schuh and made popular by the well known French puzzler reporter Pierre Berloquin.

Solution

Jud McCranie has solved the question 1 (23/12/2000):

"...for any 9 consecutive numbers to fill into a 3x3, you must have 5 even numbers and 4 odd ones, or 4 even numbers and 5 odd numbers. They must alternate odd/even in the square. The center cell plus each of the four cells touching it sum to four consecutive odd numbers, but one of those must be divisible by 3, so it can't be prime, unless it is 3. But if one of them is 3, those four numbers must be 3, 5, 7, and 9, and 9 isn't prime."

He has also sent a solution for the case 10x10:

 1 2 3 4 7 6 5 8 9 10 12 11 20 27 16 13 18 23 14 33 17 26 21 32 15 28 19 24 29 38 30 41 62 35 44 39 22 37 42 59 31 48 65 36 53 50 51 46 25 54 40 61 66 43 60 47 56 57 82 49 63 76 73 58 91 90 83 74 75 88 86 81 100 79 72 77 80 99 52 85 93 70 97 34 67 96 71 68 45 64 98 69 94 55 84 95 78 89 92 87

His method "...is a brute force one - start filling in the first row, fill in a number that forms a prime when summed to the number to the left of it and the number above it (if they exist), and proceed. If you get to a location that you can't fill, back up and try another number.". His largest primal square sent is now 13x13.

***

I (C.R.) have gotten a solution to the 20x20 case with a method that (I think) should be easily improved in order to get solutions for any n value.

This is the method:

1. Use the value n^2 in the cell north-east.

2. Assign all the other values to each cell as the largest primal-valid & non-used number, proceeding by rows from up to down, and by columns from left to right.

3. If the complete assignation to the whole matrix is not possible then - while possible - decrease by one the value for the north-east cell and go to step 2; or halt when there are no more valid values for this cell.

Using the above procedure I got this solution for n=20:

 225 394 393 380 389 398 399 388 385 384 377 396 391 382 387 400 397 390 383 386 392 267 376 381 362 371 320 363 298 355 306 347 336 337 364 369 322 379 378 365 395 374 285 358 315 368 341 290 309 304 313 330 323 354 319 340 361 372 305 326 366 353 356 303 344 375 302 357 352 349 370 331 360 373 328 333 286 367 342 335 343 348 251 350 297 334 339 274 325 294 307 346 301 318 289 310 321 292 277 324 316 283 258 359 272 327 314 345 268 253 270 271 300 299 288 259 250 351 280 223 291 208 241 282 275 332 329 248 273 226 217 232 247 210 311 198 211 256 243 244 308 279 262 295 312 287 284 293 230 261 202 255 184 199 180 281 276 265 214 235 269 338 171 196 187 234 257 264 227 296 207 254 249 190 229 228 233 168 205 252 278 263 260 201 172 175 246 245 222 167 242 237 212 231 118 193 216 215 204 317 221 240 239 218 165 142 151 186 197 266 191 206 177 170 219 238 181 132 185 224 236 203 194 179 188 195 112 145 192 155 182 131 176 213 220 163 150 161 152 159 183 164 189 200 209 158 111 166 115 162 149 120 173 140 153 154 157 156 125 104 148 129 178 93 98 135 146 147 136 121 108 143 174 137 86 87 124 127 144 119 169 100 139 130 141 128 123 160 133 106 91 138 103 126 113 110 117 64 85 114 102 97 94 99 92 105 134 63 46 67 90 101 96 71 80 83 116 75 88 109 95 84 79 58 81 76 33 74 57 82 49 78 61 66 47 56 107 122 69 70 72 65 48 55 28 73 40 39 50 21 52 31 42 41 62 51 32 77 20 27 59 44 53 54 43 36 7 34 9 38 45 22 37 60 89 8 35 26 17 14 68 29 30 13 24 23 6 25 4 15 16 1 10 19 18 11 12 5 2 3

This simple & mechanical procedure is successful without any other refinement for n = 7(39), 8(62), 13(111), 16(238), 17(165), 19(65), 20(226), 21(237), ... In parentheses is the north-east cell value (the largest or first in descending order) for the corresponding nxn square.

I guess that with a light refinement this strategy may work out solutions for all n values.

***
One day after (25/12/2000)I got the following solutions:
30(492), 40 (1336) . In order to get these examples my code used 37 minutes & 1hr.37minutes, respectively, running in a 400 Mhz PC.

***

Paul Jobling produced (29/12/2000) his own code and has sent solutions for the 45x45, 50x50, 100x100 & 150x150 primal square cases. If anybody wants the solutions I can send them on request. Regarding his method, he wrote:

My program works as follows. The order is to go across a line, then down a column. For example, for a 6x6 it would do them in the following order:

1  2  3  4  5  6
7 12 13 14 15 16
8 17 21 22 23 24
9 18 25 28 29 30
10 19 26 31 33 34
11 20 27 32 35 36

Note that this does not matter so much for simple squares, but when searching for one which has the full torus property, this allows you to check the torus conditions sooner.

I work from n^2 downwards, and place the largest unused value in each cell in turn (in the order outlined above). I then check that the number is valid by checking the sum with the number on the left and the number above. If either of these sums is not prime I decrement the number and test again. If I get to 0, I backtrack to the previously filled in square and decrement its value (in fact, rather than decrementing I subtract two, as the following paragraph will make clear).

The program only works for even values of n. To speed up the search I impose the following conditions: that the top left contains an even number, so the top row is even, odd, even, etc; the second row is odd, even, odd, etc; etc. Due to the symmetries I also constrain that the cell to the right of the top left must contain a higher value than the cell underneath the top left - this halves the search time.

My program can generate about 1 million partial valid positions per second on this 500 MHz PIII (where 'partial valid' means that all of the numbers that have been placed in the cells so far match the primality criteria with their neighbours). The inner loop, which find partial valid positions, is written in assembler. Outside this inner loop is just some code which writes out the current position to the screen every 2^20 iterations, and sees if a solution has been found and writes it out to a file if it has.

The main speed up is obtained by using pre-initialised arrays wherever possible - for example, the primality check is just a lookup into an array. This makes the assembly inner search loop just 35 instructions long.

***

He also says that no magical & primal square 4x4 was found.

***

Regarding the "full torus condition" definition he did it the following way, on my request:

"Each number in a cell is a distance y from an edge. The sum of this number with the number at the distance y in from the opposite edge must also be prime. Note that these are all four edges. For example, in the 8x8 square

.  .  .  .  .  .  .  .
.  .  a  .  .  b  .  .
.  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .
.  .  c  .  .  d  .  .
.  .  .  .  .  .  .  .

a+b must be prime, as must a+c, b+d, and c+d."

***

This is an example of an 8x8 primal square that I (C.R.) have produced with a very primitive code mainly & just  to illustrate the full torus condition, but it is not a real solution because it uses numbers greater than 64 & non-consecutive.

 28 99 158 155 156 125 152 129 151 142 135 44 137 146 87 22 132 109 148 93 140 123 154 79 61 120 121 136 57 106 73 150 138 103 76 147 134 117 124 133 145 88 63 104 89 122 75 118 82 69 128 153 74 105 92 159 111 130 21 86 107 32 141 110

Hopefully soon Paul will provide a real solution of this kind of primal squares. He is working right now in the 6x6 case. By his way Jean Charles Meyrignac will attempt to make an exhaustive search for the magic 6x6 primal square.

***
The 3/1/2001 Paul Jobling announces "I have completed the search and found no 6x6 with the full torus property".

***

 Records   |  Conjectures  |  Problems  |  Puzzles